前言
扩展欧几里得是用来求不定方程如：(ax+by=c)的一组特解.其中(a,b,c)为已知整数,(gcd(a,b)|c).这样，不
定方程才有解.
讲解
我们可以将问题转化为求(ax+by=gcd(a,b))，最后(x,y)同乘(c/gcd(a,b))即可得到一个解
根据辗转相除法，我们直接推一波式子
[ax+by=gcd(a,b)=gcd(b,a\%b)=bx'+(a\%b)y'=bx'+(a-a/b*b)y'
]
我们将(a,b)看成变量，就可以得到：
[egin{cases}
x=y'\
y=x'-a/b*x
end{cases}]
于是可以递归求解
当到递归底层，即(b=0)时，此时的(a)即为最初的(gcd(a,b))，所以此时(x=1,y=0)
当然我们在写法上可以稍微改一改，使代码更短
代码
void exgcd(int a,int b,int &d,int &x,int &y)
{
if(!b) d = a,x = 1,y = 0;
else
{
exgcd(b,a%b,d,y,x);
y -= a/b*x;
}
}