扩展欧几里德

扩展欧几里德算法

　　要是 a*x + b*y = gcd(a,b) ，则一定存在整数对(x0 , y0)使其有解

　　则 x = x0 + (b/gcd)*t , y = y0 - (a/gcd)*t 是不定方程的通解

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

　　又因为 gcd(a , b) = gcd(b , a % b);

　　所以 b*x1 + (a % b)*y1 = gcd (此时a = b , b = a % b)
　　gcd = b*x1 + (a - (a/b) * b) * y1;
　　= b*x1 + a*y1 - (a/b) * b * y1;
　　= a*y1 + b*(x1 - a/b*y1);

　　x = y1;
　　y = x1 - a/b * y1;

　　依次类推
　　当 b = 0 时
　　a = gcd;

　　定理1 gcd(a,b)是ax+by的线性组合的最小正整数，x，y∈z;

　　定理2 如果ax+by=c，x，y∈z；则c%gcd==0;

　　定理3 如果a，b是互质的正整数，c是整数，且方程
　　ax+by=c

代码如下：

int exgcd(int a , int b , int &x , int &y) {
    int res = a;
    if(!b) {
        x = 1 , y = 0;
    }
    else {
        res = exgcd(b , a % b , x , y);
        int temp = x;
        x = y;
        y = temp - a / b * y;
    }
    return res;
}