数论 扩展欧几里得算法
欧几里得算法，就是gcd的辗转相除法。
\[gcd(a,b)=gcd(b,a\mod b)
\]
\]
扩展欧几里得算法解决如下形式的问题，设存在a和b，求如下方程
\[x\times a+y\times b=gcd(a,b)
\]
\]
带入辗转相除法，得到
\[x' \times b + y' \times (a-\lfloor \frac{a}{b} \rfloor\times b)=gcd(a,b)
\]
\]
简单整理一下，得到
\[a\times y'+b\times (x'- \lfloor \frac{a}{b} \rfloor \times b)=gcd(a,b)
\]
\]
因此，得到了
\[x=y'
\]
\]
\[y=x'- \lfloor \frac{a}{b} \rfloor \times b
\]
\]
这是一种递归算法，递归的边界显然就是
\[gcd(a,b) \times 1 + 0 \times 0 =gcd(a,b)
\]
\]
逐层返回，带入式子即可解决
板子：
int exgcd(int a,int b,int &x,int &y){
if(b==0){
x=1; y=0;
return a;
}
int r=exgcd(b,a%b,x,y);
int tmpx,tmpy;
tmpx=y; tmpy=x-a/b*y;
x=tmpx; y=tmpy;
return r;
}
扩展欧几里得解出来之后，是个通式
\[x=x_0+b\div gcd(a,b) \times t
\]
\]
\[y=y_0-a\div gcd(a,b) \times t
\]
\]
应用：求解乘法逆元
求a在m意义下的乘法逆元p，且a，m互质
\[a\times p\equiv 1 (\mod m) \Rightarrow a\times p + m\times q=gcd(a,m)=1
\]
\]
那么，求解一下exgcd(a,m,x,y)，x即为a在m意义下的乘法逆元。注意，x有可能小于等于0，加上一个m即可。
原文链接: https://www.cnblogs.com/ticmis/p/13210757.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/360401
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
