扩展欧几里德

扩展欧几里德通常用于求出二元一次方程的解，类似a*x+b*y=c(a,b均不为0)的方程，a,b,c都是整数，x、y的整数解。

1 判断是否有解
整数二元一次不定方程有解的充分必要是gcd(a,b)|c。如果不能整除则无解。

2 扩展欧几里德求特解

欧几里德给出了计算a*x+b*y=gcd(a,b)的解法。

之前写的太复杂自己都快看不懂了，删了重写一遍，看了一下知乎里的证明，链接https://www.zhihu.com/question/30067108，感觉很简洁，斗胆拿来用一下。

对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得

a*x+b*y = gcd(a , b); ①

根据欧几里德原理

gcd(a , b) = gcd(b , a mod b)

将gcd(b,a mod b)表达为①式的形式，即

a*x+b*y = gcd(a , b)

= gcd(b , a mod b)

= b * x1 + (a mod b) * y1

= b * x1 + (a - a / b * b) * y1 即

a*x+b*y = b * x1 + (a - a / b * b) * y1

化简上式，得

a*x+b*y = a*y1 - b*a/b*y1 + b*x1 ，即

a * x + b * y

= a * y1 + b * (x1-a/b*y1)

所以

x=y1

y=x1 - a/b*y1

于是我们得到了这样一段代码

 1 void exgcd(int a, int b, int &d, int &x ,int &y)
 2 {
 3     if ( !b )
 4     {
 5         d = a;
 6         x = 1;
 7         y = 0;
 8         return;
 9     }
10     int x1,y1;
11     exgcd( b , a % b , d , x1 , y1 );
12     x = y1;
13     y = x1 - ( a / b ) * y1;
14     return ;
15 }

再简化一下可以得到

 1 //ax+by=gcd(a,b),d为最后求出的gcd(a,b)
 2 void ex_gcd(LL a,LL b,LL &x,LL &y,LL &d){
 3     if(!b){
 4         d=a;
 5         x=1;
 6         y=0;
 7         return;
 8     }
 9     ex_gcd(b,a%b,y,x,d);
10     y=y-a/b*x;
11 }

上面代码中，通过交换x,y的位置，原本y1的位置变成x，x1的位置变成y相当于执行了x=y1，y=x1，因为y = x1 - ( a / b ) * y1，所以还需要y-=a/b*x。