欧几里得定理（nyoj775）

灰太狼 2022-08-29 04:23 168阅读 0赞

A了一道题目，深入学习了一下欧几里得定理，记录一下：

我们平常了解的欧几里得定理就是求两个数最大公约数。

求最大公约数的定理是：设a，b是任意两个正整数，则gcd（a，b）=Rn，其中Rn是广义欧几里得除法中最后一个非零余数。算法描述

int gcd(int x,int y)
    {
        int t=x%y;
        while(t)
        {
            x=y;
            y=t;
            t=x%y;
        }
        return y;
    }

但是当你遇上一个这样一个问题该怎样快速解决呢？

对于任意两个正整数a和b，必定存在一对整数s、t使得sa+tb=gcd(a,b)。

给出a，b，求s，t。

定理：设a，b为任意两个正整数，则Sn\*a+Tn\*b==gcd（a，b），对于n=0,1,2...这里的Sn，Tn可归纳

S0=1,S1=0, S（j）=S（j-2）-q（j-1）\*S（j-1）...

T0=0,T1=1, T(j)=T(j-2) - q(j-1)\*S(j-1)

由此可求出s和t。

题目描述：[http://acm.nyist.net/JudgeOnline/problem.php?pid=775][http_acm.nyist.net_JudgeOnline_problem.php_pid_775]

代码：

#include <cstdio>
    #include <cmath>
    
    int s[1005],t[1005];
    int main()
    {
        int a,b;
        s[0]=1,s[1]=0;
        t[0]=0,t[1]=1;
        while(~scanf("%d%d",&a,&b))
        {
            if(a+b<0&&a==b)
                break;
            int x,k=2;
            while(b)
            {
                s[k]=s[k-2]-a/b*s[k-1];
                t[k]=t[k-2]-a/b*t[k-1];
                //printf("%d %d\n",s[k],t[k]);
                x=a%b;
                a=b;
                b=x;
                k++;
            }
            printf("%d %d\n",s[k-2],t[k-2]);
        }
        return 0;
    }

[http_acm.nyist.net_JudgeOnline_problem.php_pid_775]: http://acm.nyist.net/JudgeOnline/problem.php?pid=775

发表评论取消回复

表情：

评论列表（有 0 条评论，168人围观）

还没有评论，来说两句吧...

相关阅读

相关欧几里得算法

一.自然语言描述：计算两个非负整数p和q的最大公约数：若q是0，则最大公约数为p。否则，将p除以q得到余数r，p和q的最大公约数即为q和r的最大公约数。二.Jav

╰+哭是因爲堅強的太久メ/ 2024年03月23日 17:45/ 0 赞/ 98 阅读

相关欧几里得算法

欧几里得算法中，计算 x, y 的最大公约数的方法是辗转相除，例如： gcd (26, 15) 26 % 15 = 1 ... 11 15 % 11 = 1 ... 4

秒速五厘米/ 2022年10月01日 13:46/ 0 赞/ 250 阅读

相关欧几里得定理（nyoj775）

A了一道题目，深入学习了一下欧几里得定理，记录一下：我们平常了解的欧几里得定理就是求两个数最大公约数。求最大公约数的定理是：设a，b是任意两个正整数，则gcd（a，b）

灰太狼/ 2022年08月29日 04:23/ 0 赞/ 169 阅读

相关欧几里得和扩展欧几里得算法

（一）欧几里得算法又称辗转相除法，是求解两个数的最大公约数的算法，基本定义为：设 a=qb+r，其中a，b，q，r都是整数，则：gcd（a，b）= gcd（b，r）利用

ゞ浴缸里的玫瑰/ 2022年08月21日 03:20/ 0 赞/ 288 阅读

相关扩展欧几里得定理

扩展欧几里德算法（注意：拓展（扩展）欧几里得算法是求解形如ax+by=1的方程组的（而且a和b是互质的，允许通过约分得到，并且求出的x如果是正数的话那一定是最小正整数，如果为负

缺乏、安全感/ 2022年06月17日 06:54/ 0 赞/ 303 阅读

相关欧几里得推扩展欧几里得

欧几里得求整数a,b的最小公约数gcd(a,b)的算法。即欧几里得算法(俗称最小公倍数算法)。有一个重要的公式如下,这个公式的证明略,百度上有. (1) g

我会带着你远行/ 2022年06月13日 09:22/ 0 赞/ 282 阅读

相关欧几里得+扩展欧几里得（理解）

-------------------- 欧几里得： -------------------- 辗转相除法代码： typedef long long

妖狐艹你老母/ 2022年06月05日 05:39/ 0 赞/ 338 阅读

相关扩展欧几里得

GCD 定义欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。结论与证明对于a,b两个正整数（a>b），gcd(a,b)=gcd(a

以你之姓@/ 2022年03月20日 07:53/ 0 赞/ 301 阅读

相关数论杂谈——欧几里得算法及扩展欧几里得

数学是oi的重要基础，所以说数论在oi中占据了非常重要的地位，因此，学好数学，对于一个oier来说也是非常重要的。 oi中的数学，其实也就和数竞并没有什么区别。欧几里得法

落日映苍穹つ/ 2021年12月23日 23:55/ 0 赞/ 398 阅读

相关欧几里得算法

一代码 package Euclid; / Copyright (C), 2020-2020, XXX有限公司 Fi

红太狼/ 2021年07月24日 16:01/ 0 赞/ 455 阅读