扩展欧几里德 求A,B的最大公约数,并求出X,Y A*X+B*Y=gcd(A,B)int ex_gcd(int a,int b,int &x,int &y){ if(b==0) { x=1;y=0; return a; } else { int r=gcd(b,a&b,y,x); y-=x*(a/b); return r; }}