推荐：https://www.zybuluo.com/samzhang/note/541890
扩展欧几里得，就是求出来ax+by=gcd(x,y)的x，y
为什么有解？
根据裴蜀定理，存在u，v使得au+bv=gcd(x,y)
证明：
这里面，c,e，就是所谓的u，v
对于ax+by=gcd(a,b)
因为gcd(a,b)=gcd(b,a%b)
ax+by=gcd(a,b)
bx1+(a%b)y1=gcd(b,a%b)
可以变成:ax+by=bx1+(a%b)y1
就是：ax+by=bx1+(a-[a/b]*b)y1
所以：ax+by=ay1+b(x1-[a/b]*y1)
所以，如果求出来y1,x1,就可以对应的求出来x，y
x=y1,y=(x1-[a/b]*y1)
不停地递归下去。
边界：
b==0 时，ax+by=gcd(a,b)
这时候，b是0，a就是gcd(a,b)，所以x=1，y随便一个值，都是一个特解。
一般让y=0 （让|x|+|y|最小 -----------Monster_Yi)
（让|x+y|最小————SD_le）
（反正我也不知道是哪一个）
实测y等于几都可以，但是0小，一般不会爆int，爆掉的几率比较小。
递归返回去，上一步的x,y根据下一步的x，y赋值就好
代码：
void exgcd(int a,int b)
{
if(b==)
{
x=;
y=;
return;
}
exgcd(b,a%b);
k=x;
x=y;
y=k-a/b*y;
return;
}
这个没有传引用，直接交换的。x，y都是全局变量。便于理解。
但是代码太丑了。
传引用：
void exgcd(int a,int b,int &x,int &y){
if(b==){
x=,y=;return;
}
exgcd(b,a%b,y,x);
y-=(a/b)*x;
}
这里的代码是上一个版本的简略版，
传入下一步的时候，x，y传入的时候就交换了，相当于x=y1,y=x1
回溯之后的，y-=(a/b)*x, 因为这个时候的x就是 y1 , y已经赋值为x1,所以直接减就可以
当然，这里最后需要的x，y就直接传进去了。
应用：
1.求ax=1(mod b) b不一定是质数。也就是求一般情况下的a的逆元（noip2012 同余方程）
2.ax+by=gcd(a,b) 可以将gcd(a,b)除下去，变成：a0x+b0y=1 同上
3.ax+by=c无整数解情况：gcd(a,b)不能整除c（左边可以提出来gcd，右边不行）
4.对于ax+by=c 的一般方程，先判断有没有解，再求出ax+by=gcd(a,b) 最后 x,y 乘上 c/gcd(a,b)
5.ax-by=c ,算出来ax+by=c , y再取相反数即可。