欧几里得算法

1.欧几里得

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

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

2.欧几里得扩展

参考：https://www.cnblogs.com/Aiahtwo/p/10894280.html

求给定的ax+by = c的一组最小正解

当c%gcd(a, b) = 0时不定式有解，即对ax+by = gcd(a, b)求出一组特解(x0, y0)，由欧几里得定律当a%b = b = 0时a即为gcd(a, b)，此时令x = 1, y = 0即为当前状态的一组解，

逐层递归由bx'+a%b*y' = gcd(b, a%b) =>  ay' + b(x'-a/b*y') = gcd(b, a%b)  可得 x = y, y = x'-a/b*y'

而对于一组特解(x0, y0)，a*c/gcd*x0+b*c/gcd*y0 = c，可知通解x = c/gcd*x0+k*(b/gcd)，y = c/gcd*y0-k*(a/gcd)，令b1 = b/gcd

则最小x = (x%b1+b1)%b1， y = (c-a*x)/b

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