扩展欧几里得算法

　　问题：ax+by=c，已知a、b、c，求解使该等式成立的一组x，y。其中a、b、c、x、y均为整数 a,b的最大公约数为gcd(a,b)。如果c不是gcd(a,b)的倍数，则该等式无解，因为等式左边除以gcd(a,b)是整数，而等式右边除以gcd(a,b)后为小数。因此，只有当c是gcd(a,b)的倍数的时候，该等式有解。这样，可以通过计算使ax1+by1=gcd(a,b)成立的x1、y1，然后有x=(c/gcd(a,b))*x1，y=(c/gcd(a,b))*y1，得到x,y。 问题就被转换为求使ax+by=gcd(a,b)成立的一组x,y。　　

　　如果b不为零，根据欧几里德定理，可以设 ax1+by1=gcd(a,b)=gcd(b,a%b)=bx2+(a%b)y2=bx2+(a-(a/b)*b)y2 化简后有x1=y2，y1=x2-(a/b)y2。因此x1,y1依赖于x2,y2，同理依次类推递归调用求出x3,y3,x4,y4……，类似于辗转相除，直到b=0时，求出xn,yn，便可以推出x1,y1的值。

 1 // 返回a,b的最大公约数
 2 int extended_euclid(int a, int b, int &x, int &y)
 3 {
 4     if(b == 0) // gcd(a, b) == a
 5      {
 6          x = 1;
 7          y = 0;
 8         return a;
 9      }
10     int n = extended_euclid(b, a%b, x, y);
11     int tmp = x;
12      x = y;
13      y = tmp - static_cast<int>(a/b)*y;
14     return n;
15 }

 　　其它解为x0 + k*b/gcd(a,b),y0-k*a/gcd(a,b)，具体参考白书P179.