扩展欧几里得算法

扩展欧几里得算法，顾名思义，由欧几里得算法扩展而来。

欧几里得的辗转相除法

欧几里得算法核心在于：gcd(a,b) = gcd(b, a%b) & 递归

证明 gcd(a,b) == gcd(b, a%b)

假设 a % b = c 则 a = x*b + c
假设 gcd(a,b) = r 则 a = A * r , b = B * r
所以 a = x * b + c 可以写成 A * r = x * B * r + c
所以 c = A * r - x * B * r
c = (A - x * B) * r (A 和 B 和 x皆为整数)
所以 c 也是 r 的整数倍
所以 gcd(b, c) = r * gcd(B, A - xB)
由于A 和 B没有除1外的公因数(如果有则 r ！= gcd(a,b))
所以 gcd(B, A - xB) = 1
gcd(a,b) == gcd(b, c) == gcd(b, a % b)

于是求两数最大公约数问题就可以用

递归解决：

gcd(a,b) == gcd(b, a%b) = gcd(a%b, b % (a%b)) = … = gcd(x,0) = x

int gcd(int a,int b){
	if(b == 0)return a;
	return gcd(b, a%b);
}

扩展

给出整数a, b, c如何求解ax + by = c的一组整数解(x,y) ？

令r = gcd(a,b)， a = A * r, b = B * r
A * r * x + B * r * y = c，两边同时除以r
A * x + B * y = c / r
因为存在整数解，所以c / r也必然为整数
只有当c为gcd(a,b)的整数倍时ax + by = c存在整数解。

问题转变为给出整数a, b如何求解ax + by = gcd(a,b) 的一组整数解(x,y) ？

掏出热乎的欧几里得套娃思想
假设 a * x1 + b * y1 = gcd(a,b)
b * x2 + (a%b) * y2 = gcd(b, a % b)

因为 gcd(a, b) = gcd(b, a %b)
所以 a * x1 + b * y1 = b * x2 + (a%b) * y2

把a % b写为a - b * a/b （此处为整除，和C语言的/运算相同）
a * x1 + b * y1 = b * x2 + (a-b*a/b) * y2
移项后得到等式ax1 + by1 = ay2 + b(x2 - (a/b) * y2)
所以 x1 = y2, y1 = x2 - a/b * y2

只要能知道x2, y2的一组整数解则可由
b * x2 + (a%b) * y2 = gcd(b, a % b)
转变为
a * x1 + b * y1 = gcd(a,b)
其中
x1 = y2
y1 = x2 - a/b * y2
回顾欧几里得的递归算法，当b = 0时
gcd(a,0) = a
同时问题也变成了ax + 0y = a
此时可以自信的给出一组整数解
x = 1 , y = 0

 int gcdEx(int a,int b,int&x,int&y){
    if(b==0){
        x=1,y=0 ;
        return a ;
    }
    else{
        int r=gcdEx(b,a%b,x,y);
        /* r = GCD(a, b) = GCD(b, a%b) */
        int t=x ;
        x=y ;
        y=t-a/b*y ;
        return r ;
    }
}