必存在一对整数(x,y) 使得a*x+b*y=gcd(a,b);

gcd（a,b）= gcd(b,a%b) （辗转相除法）

又 a*x1+b*y1=gcd(a,b)=gcd(b,a%b)=b*x2+(a%b)*y2;

又b*x2+(a%b)*y2=b*x2+(a-[a/b]*b)*y2=a*y2-b*(x2-[a/b]*y2);

对比系数得 x1=y2,y1=x2-[a/b]*y2;

按以上递归得最后必有x*a=a（这个a表示上面的a和b的最大公约数）; 即x=1 
void exgcd(int a,int b,int &d,int& x,int &y){
    if(!b){
        d=a;x=1;y=0;
        return ;
    }
    exgcd(b,a%b,d,y,x);
    y-=a/b*x;
}


对于上诉代码 调换了x,y 也就导致了 y1=x2,并且y2=x1; 所以有 y-=x*(a/b);

用d记录最小公倍数，如果a*x+b*y=c,c != k*d 则无整数解