avatar

扩展欧几里得算法(ExGCD)代码

扩展欧几里得算法(ExGCD)代码

之前的数学笔记中讲过这个算法,所以这里把代码贴一下。

1
2
3
4
5
6
7
8
9
10
11
12
int exgcd(int a, int b, int& x, int& y) {
if(b == 0) {
x = 1;
y = 0;
return a;
}
int xp, yp;
int g = exgcd(b, a % b, xp, yp);
x = yp;
y = xp - a / b * yp;
return g;
}
文章作者: Ender
文章链接: https://www.ender.xin/post/48ef8cc9.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Ender's blog
打赏
  • 微信和支付宝
    微信和支付宝

评论