证明：我们先想证明\(gcd(a,b)=gcd(b,a\%b)\)
我们先证明\(gcd(a,b)=gcd(a-xb)\)
这样，当\(x=1\)时，他就是辗转相除法\(gcd(a,b)=gcd(b,a-b)\)
当\(x=\frac{a}{b}\)，且除法向下取整，则此时\(gcd(a,b)=gcd(b,a\%b)\)
所以只要证明出来\(gcd(a,b)=gcd(a-xb)\)对于任意的\(x\)成立，我们就可以证明欧几里德算法成立
真正的证明
设\(gcd(a,b)=c,gcd(b,a-xb)=d\)
根据性质，可以写出
\(\because c|a,c|b\)
\(\therefore c|(a-xb)\)
\(\therefore c|gcd(b,a-xb)\Leftrightarrow c|d\)
\(\because d|b \therefore d|(xb)\)
又\(\because d|(a-xb) \ \therefore d|a\)
\(\therefore d|gcd(a,b)\Leftrightarrow d|c\)
\(\because d|c\ \&\ c|d\)
\(\therefore c==d\)
所以，我们可以证明欧几里德算法成立
代码：
inline int gcd( int x , int y ){
return y == 0 ? x : gcd( y , x % y ) ;
}
实质上，扩展欧几里德解的是\(a*x+y*b=gcd(x,y)\)，解出来的\(x,y\)是绝对值最小的解，有可能是负数。
那么，对于任意已知\(a,b,c\)的
我们都可以通过扩展欧几里德来求解，我们可以考虑先给全部式子都乘上 \(\large\frac{gcd(a,b)}{c}\)
那么，式子就会变成
这样我们发现其实对于a,b这个式子就是一个扩展欧几里德了，只不过我们解出来的\(x_0,y_0\)分别是\(x_0*\frac{gcd(a,b)}{c},y_0*\frac{gcd(a,b)}{c}\)，我们只需要把求出来的\(x,y\)都乘上\(\frac{c}{gcd(a,b)}\)就可以了
但是我们发现\(\frac{c}{gcd(a,b)}\)是整数当且仅当\(c \% gcd(a,b)==0\)，这也就是上文中要求的由来
但是，我们还可以发现，其实这个方程肯定有无限组解，我们只求出来了一组特殊解，怎么推广到全部呢？
我们可以把\(a*x+b*y\)写成
那么，我们求出来的\(x,y\)都可以变成\((x-k*b),(y+k*a)\)
所以现在我们只需要考虑\(k\)的取值范围就行了
但是观察了许久，发现并没有什么范围
于是我们想，如果能让\(k\)取遍他的定义域的同时求出所有解，那么这个\(k\)一定是唯一的，且不能再小，再小就会得到不正确的解，再大就不能得到所有解
我们让\(k\)最小不就行了？
我们发现，我们只需要满足\(k*a\)和\(k*b\)都是整数，其他方面没有对\(k\)有过多要求
所以\(k\)的最小值就得到了，我们得\(k=\frac {1}{gcd(a,b)}*t \ |t\in Z\)
易得t取遍z的时候，所有解集就得到了
所以
对于
还有一个事情，就是最小正数解，我们只需要把\(x\)搞成\(((x\%b)+b)\%b\)就可以了，其实也就是\(x<0\)的时候\(x+=\frac{b}{gcd(a,b)}\)
说了这么多，忘记证明扩展欧几里德的原理了
为什么我们可以求出\(x,y\)?
根据欧几里德算法，我们知道
我们还知道，当\(b=0\)时，\(a=gcd\)，算法停止
所以我们可以得到\(a*1+b*0=gcd\)
得到一个状态后，我们只需要得到如何转移状态即可
由于
又由于\(a\%b==a-(a/b)*b\),这里除法向下取整
我们展开模运算和gcd，可以得到
代码
inline 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 = t - y * ( a / b ) ;
return ans ;
}
学会这个东西，有什么用处呢？其实最大的用处是求乘法逆元
我们知道\(（a/b）\%c \not=((a\%c)/(b\%c)\)，所以，如果\(a/b\)很大的话，我们如何计算呢？
这里就要引入一个乘法逆元,我们可以找到一个数\(x\),使得\(（a/b）\%c =((a\%c)*(x\%c))\%c\)
这个\(x\)就是\(b\)关于\(c\)的乘法逆元
\(x\)的计算方法是\(x*b≡1(mod\ c)\),由于\(b,c\)已知，我们只需要用扩展欧几里德解\(x*b+t*c=1\)
得到一个\(x\)，把\(x\)变成最小正整数解就可以了
在这种计算方法下，要求\(gcd(b,c)\%1=0\),也就是\(gcd(b,c)=1\)
还有一个求法，费马小定理\(x=b^{c-2}\),当\(p\)是质数的时候成立，需要打一个快速幂。
这两种复杂度都是\(log(n)\)，都用于求一个数的乘法逆元，扩欧的要求更少。
如果一道题我们需要求\(1~n\)的乘法逆元，那么我们的复杂度是\(nlog(n)\)，但是其实还有一种更快的方法
证明不太会，以后再说，直接给代码
int inv [N] ;
inv [1] = 1 ;
for( int i = 2 ; i <= n ; i ++ )//i mod p 的逆元
inv [i] = ( p - （ p / i ） ) + inv [p % i] % p ;
联系客服
