扩展欧几里得
必存在一对整数(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; 即x=1;
void exgcd(int a,int b,int &d,int &x,int &y){ if(!b){d=a;x=1;y=0;} else {gcd(b,a%b,d,y,x);y-=x*(a/b);} }
对于上诉代码 调换了x,y 也就导致了 y1=x2,并且y2=x1; 所以有 y-=x*(a/b);
用d记录最小公倍数，如果a*x+b*y=c,c != k*d 则无整数解
