拓展欧几里得算法
先来看看一个重要的基本定理
裴蜀定理
对于整数a,b，他们关于x,y的线性不定方程\(ax+by=d\)，设\(gcd(a,b)=g\)，则可证明\(g|d\)，换句话说，就是g是a,b的最小线性组合。
证明：
设\(ax+by=d\)，\(g=gcd(a,b)\)，设\(ax+by\)的最小值为s，
\(\because\) \(g|a,g|b\)
\(\therefore\) \(g|d\),\(g|s\)
设\(q=[\frac{a}{s}].则r= a\mod s=a-q*s=a-q*(ax+by)=a(1-qx)+b(-qy)\)。
可见r也是x,y的线性组合，又r是s的余数，\(r\in [0,s-1]\)，又s是最小线性组合，\(\therefore r=0\)。
推出\(s|a\)，同理有\(s|b\)，则\(s|g\),又已经有\(g|s\)，所以\(g=s\)。可知g是ax+by的最小线性组合。
推论：
a和b互质的充要条件是存在x,y使\(ax+by=1\)，因为由上面的证明结论知道d（这里是1）一定是gcd(a,b)的倍数。
其实还可以推广到一堆数互质（这些数的gcd为1）的情况。
拓展欧几里得
我们知道，一般的 欧几里得算法是来求两个数的最大公因数的，但是拓展欧几里得可以走得更远，也就是说，它不仅仅求一个gcd，而是可以求出一些额外的东西。前面的定理说了a,b线性组合最小是\(gcd(a,b)\)，我们就可以求出\(ax+by=gcd(a,b)\)对应的x,y出来。
怎么求呢？我们已经知道当欧几里得算法递归到终点时，gcd(a,b)中的b已经是零，也就是说，这个时候\(a*1+b*0=a\)，x=1，y=0，我们就可以在这时反推上去求解最终的x,y
现在是递归返回过程的某一步，我们已经求得了b和a%b的gcd，还有此时的x1,y1，就是说\(b*x1+a\%b*y1=gcd\)，要怎么求a,b的x,y呢？
我们知道\(a\%b=a-[\frac{a}{b}]*b\)，\(gcd=b*x1+(a-[\frac{a}{b}]*b)*y1=b*x1+a*y1-[\frac{a}{b}]*y1*b=a*y1+(x1-[\frac{a}{b}]*y1)*b=a*x+b*y\)
可以看出\(x=y1,y=x1-[\frac{a}{b}]*b\).递归返回时即可更新掉x,y的值返回即可。
代码：
int ex_gcd(int a,int b,int& x,int& y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
int ans = ex_gcd(b,a%b,x,y);
int tmp = x;
x = y;
y = tmp-a/b*y;
return ans;
}
拓展欧几里得求逆元
什么是逆元？\(a*x\equiv{1}\mod m\)，这里\(x\)就是a的逆元。逆元有什么用呢？*如果我们要求\(a/b \mod m\)的值，而a，b很大，设b的逆元为x，这个时候注意到\((a/b)*x*b=(a/b)\mod m=a*x\mod m\)巧妙地把出发转换成了乘法。
为什没求逆元跟欧几里得算法联系起来了呢？根据上面裴蜀定理，我们知道gcd是a,b两个数线性组合的最小值，其他组合值都是gcd的倍数，当gcd为1时，a,b互质，满足\(ax+by=1\)，移项得\(ax=-by+1\),即\(ax\equiv1\mod b\),此时的x就是逆元。实际上线性不定方程组有无穷多解，这里只求正的最小的逆元。
代码
int cal(int a,int m)
{
int x,y;
int gcd = ex_gcd(a,m,x,y);
//cout << "a " << a << " m " << m << " x " << x << " y " << y << endl;
if(1%gcd!=0) return -1;
x*=1/gcd;
m = abs(m);
int ans = x%m;
if(ans<=0) ans += m;
return ans;
}
这里1%gcd是看gcd是不是1，前面说了，d（这里是1）应该是gcd的倍数，而且不互质的两个数没有逆元。\(x*=1/gcd\)实际上更一般的写为\(x*=d/gcd\)，也就是求解一般不定方程\(ax+by=d\)的解，因为d是gcd的倍数，我们就把倍数乘上去解得\(x'=x*(d/gcd)\)。m是负数的话，我们取|m|，如果求出来x是负数，就x%|m|,结果再加上|m|即可。（因为有无穷个解，通解为\(x+m*t\)）
参考文章
zhj5chengfeng，扩展欧几里德算法详解，https://blog.csdn.net/zhjchengfeng5/article/details/7786595
leader_one，欧几里得算法/扩展欧几里得算法，https://blog.csdn.net/leader_one/article/details/75222771
Jollwish，扩展欧几里得算法，https://wenku.baidu.com/view/a75fdfd376a20029bd642de5.html