拓展欧几里得算法

裴蜀定理：

对任意的a,b，有 a*x+b*y = gcd(a,b);
当b=0，有 gcd(a,b) = a;

当b≠0：

b*y + (a - [a/b]*b)*x = gcd(a,b);

b*y + a*x - [a/b]*b*x = gcd(a,b);

a*x + b*(y-[a/b]*x) = gcd(a,b);

发现，x 不变， y -= [a/b]*x；

模板：

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