扩展欧几里得

讲扩欧前先来回顾以下gcd，直接上代码
int gcd(int a,int b)
{
if(b==0) return a;
return gcd(b,a%b);
}
扩展欧几里得算法：对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。
第一种情况：当b==0时，很明显gcd(a,b)=a,x=1,y=0;
第二种情况：设ax1+by1=gcd(a,b),bx2+(a mod b)y2=gcd(b,a%b)
因为gcd(a,b)=gcd(b,a%b) 所以有ax1+by1=bx2+(a mod b)y2；又因为a mod b=[a-(a/b)b],所以等量替换得到
ax1+by1=bx2+[a-(a/b)b]y2，把括号展开也就是，ax1+by1=ay2+bx2-(a/b)by2;
所以我们可以得到x1=y2,y1=x2-(a/b)y2
也就是说只要我们直到这一次x,y的解 就可以通过递归求得上一层x,y的解，逐步递归当b==0时，也就是终止条件了，因为此时只有一个解。
所以整个扩欧代码可以总结为
int exgcd(int a,int b,int& x,int& y)
{
if(b==0)
{
x=1,y=0;return a;
}
int ans=exgcd(b,a%b,x,y);
int t=x;
x=y;
y=x-(a/b)y;
return ans;
}
这个代码还可以简化下写成
int exgcd(int a, int b, int& x, int& y)
{
if(b == 0)
{
x = 1;
y = 0;
return a;
}
int ans = exgcd(b, a%b, y, x);
int t = x;
y = y - a/bt;
return ans;
}