扩展欧几里德算法
提到扩展欧几里德算法，先简要介绍下欧几里德算法，又称辗转相除法，用于计算两个整数a和b的最大公约数（Greatest Common Divisor(GCD)）。
为证明gcd(a,b)=gcd(b,a mod b)，只需证明
(1)gcd(a,b) | gcd(b,a mod b)
设d=gcd(a,b) 则d|a且d|b
a mod b=a-qb (设q=[a/b])
由d|ax+by 则d|a mod b
所以d| gcd(b,a mod b)
(2)gcd(b,a mod b) | gcd(a,b)
设d=gcd(b,a mod b)
则d|b且d|a mod b
a=qb+(a mod b) (q=[a/b])
得d|a
所以d|gcd(a mod b)
求解a和b的最大公约数中，a可以表示为kb+r，则r =a mod b，假设d是a和b的一个公约数，则有d|a，d|b，r = a - kb,因此d|r（因为d是a的约数，又是b的约数，所以也是他们的多项式的约数）,所以d是(b,a mod b)的公约数。所以在这不断代换中，a 必然＞ｂ，每次将ａ换成ｂ，ｂ换成ａmod b, a ,b 不断减小。直到b为0时，此时a为他们的最大公约数。
1 int euclid(int a,int b) 2 { 3 if (b==0) 4 return a; 5 else 6 return euclid(b,a%b); 7 }View Code
而扩展欧几里德算法是用来求解已知a，b，求一组x，y使得a * x + b * y =Gcd(a,b)(这个解一定存在，数论定理)
因为Gcd(a,b)=Gcd(b,a%b),所以a * x + b * y = Gcd(a,b) = Gcd(b,a%b)。得b * x + (a%b)*y = b * x + (a - a/b*b)*y,这里的((a - a/b*b)*y)不难得出，之前是a%b。现在我想得到这个数，怎么来呢。首先a/b，得到一个整数，在a！=b的情况下，这个整数再乘以b之后是不等于a的。所以余数就是这里的差值。即a - a/b*b。如果a==b，那么Gcd==a==b。继续，b * x + (a%b)*y = b * x + (a - a/b*b)*y。展开得b*x + a*y - a/b*b*y，合并得a*y + b*(x-a/b*y).这样，因为a，b都在减小，当b=0时，可以得出x=1,y=0，此时递归回去可以求出x，y。
1 int extended_gcd(int a, int b, int &x, int &y) 2 { 3 int ret, tmp; 4 if (!b) 5 { 6 x = 1; 7 y = 0; 8 return a; 9 } 10 ret = extended_gcd(b, a % b,x, y); 11 tmp = x; 12 x = y; 13 y = tmp - a / b * y; 14 return ret; 15 } 16View Code
对于方程a * x + b * y=c，该方程等价于a*c ≡ c(mod b);有整数解的充要条件是 c % gcd(a,b)==0。(定理)
所以方程 a*x+b*y=n；我们可以先用扩展欧几里德算法求出一组x0,y0。即 a * x0 + b * y0 = Gcd(a,b)；
然后两边同时除以Gcd(a,b) ，再乘以n。这样就得到了方程 ：a * x0 * n / Gcd(a,b) + b * y0 * n / Gcd(a,b) =n；从而求出一个解
通过扩展欧几里德求的是ax + by = Gcd(a, b)的解，令解为(x0, y0)，代入原方程，得：ax0 + by0 = Gcd(a, b)，
如果要求ax + by = c = Gcd(a, b)*c'，可以将上式代入，得：
ax + by = c = (ax0 + by0)c'，则x = x0c', y = y0c'， c' = c / Gcd(a,b)
这里的(x, y)只是这个方程的其中一组解，x的通解为 { x0c' + k*b/Gcd(a, b) | k为任意整数 }，y的通解可以通过x通解的代入得出
若gcd(a,b)=1，即a、b互质，且x0,y0为a*x+b*y=n的一组解，则该方程的任一解可表示为：x=x0+b*t，y=y0-a*t；且对任一整数t，皆成立。
这样我们就可以求出方程的所有解了，但实际问题中，我们往往被要求去求最小整数解，所以我们就可以将一个特解x。令t=b/gcd(a,b)=1，特解x=(x%t+t)%t；
poj题目链接：
青蛙的约会 、 C Looooops 、The Balance 、Business Center 、 Comfort
