gcd(a,b)=gcd(b,a%b)
gcd(a,b)中要求a，b是非负数 

//xa+yb=gcd
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;
}
ax+by=d通过exgcd求出了x0，y0（ax+by=gcd的解）后求出x和y的通解：
x=（x0-b/gcd）*k
y=（y0+a/gcd）*k

另类的方法（不常用，不实用） 

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