扩展欧几里得

欧几里得：

1 void gcd(int a, int b) {
2     return gcd(b, a % b);
3 }

扩展欧几里得：

根据裴蜀定理可以求出ax+by=c的直线上的所有整数解。

存在x和y使得ax+by=gcd(a,b)成立，而根据辗转相除法，方程最终态为a=gcd(a,b)，b=0，此时x=1，y=0，将此解迭代回去即可求出x与y的最初解。

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;
}

返回值为a与b的最大公约数