扩展欧几里得算法
欧几里得算法
欧几里得算法是用来求最大公约数的，gcd(a,b)=gcd(b, a%b)，如此递归下去，直到a%b==0，然后返回。
最终，gcd(a,b)=gcd(c,0)，其中，a,b的最大公约数就是c
扩展欧几里得算法（exgcd)
扩展欧几里得算法是解决诸如：求整数x和y使得ax+by=gcd(a,b)的问题的。
这里借用oi-wiki中的证明：
然后，代码如下：
int Exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1;
y = 0;
return a;
}
int d = Exgcd(b, a % b, x, y);
int t = x;
x = y;
y = t - (a / b) * y;
return d;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021年9月7日20，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录