本文共 1322 字，大约阅读时间需要 4 分钟。

是用来在已知a, b求解一组x，y，使它们满足贝祖等式： ax+by = (a, b) =d（解一定存在，根据中的相关定理）。

扩展欧几里德常用在求解模及方程组中。

 

首先，证明一下gcd(a,b)==gcd(b,a%b)

设gcd(a,b) = k

a = n1 * k b = n2 * k a%b = (n1%n2)*k b = n2 * k 现在只需证n2 和 n1%n2 没有公因子 假设有公因子,为r n2 = num2 * r n1%n2 = num1 * r n1 = k*n2 + num1*r n1 = (k*num2+num1)*r n1和n2有公因子,这与设gcd(a,b) = k矛盾,因为如果n1和n2有公因子,那么gcd(a,b)=k*r 所以gcd(b,a%b) = gcd (a,b)

（）

由上面的等式，我们可得：

∵gcd(a,b)==gcd(b,a%b)

∴a*x1+b*y1==b*x2+(a%b)*y2　　　　　　　　　　　　//一定有整数解x,y

∵在计算机科学里a%b的实际运算是 a-(a/b)*b　　　　　　　　//a/b因为都是整形变量，所以计算时a/b==⌊a/b⌋

∴a*x1+b*y1==b*x2+(a-(a/b)*b)*y2

整理可得a*x1+b*y1==a*y2+b*(x2-(a/b)*y2)

即x1=y2，y1=x2-(a/b)*y2

显然，我们只要找到递归边界，就可以不断求解，直到得出答案

辗转相除法：

int gcd(int a,int b)

{

return b==0?a:gcd(b,a%b);

}

也就是说边界是 a*x+b*y==gcd(a,b)==a　　//因为此时b==0

那么现在x是不是就是1，y可以取任意整数

 

以下为最简c++语言写法：

void gcd(int a,int b,int &x,int &y)

{

　　if (b==0){x=1,y=0;return;}　　gcd(b,a%b,y,x); 　　　　　　　　 //注意x，y的位置　　y-=a/b*x;}

 

这里的引用解决了x1=y2，所以仅剩y1=x2-(a/b)*y2；

又是因为引用，y1=x2，x1=y2；

所以y1=y1-(a/b)*x1；

不得不说，能首先写出这个的大佬，的确思维逻辑很好！！！

 

 

当然，不用引用的话，返回一个结构体也行（貌似会更好理解）

struct ans

{

　　int x,y;};ans gcd(int a,int b){

　　ans myans,t;　　if(b==0){myans.x=1,myans.y=0;return myans;}　　t=gcd(b,a%b);　　myans.x=t.y;　　myans.y=t.x-a/b*t.y;　　return myans;}

 

可以试一下改变递归边界中的y的值，会有惊喜；

 

我们得出了一组解  x,y

显然a*x0+b*y0==a*x+b*y　　//x0,y0为已得解，x,y为其他答案

x=x0+k*b，y=y0-k*a　　　　//k为整数，其实你将x，y带入原式，就会发现显然成立

 

转载地址：http://lqhof.baihongyu.com/