扩展欧几里得算法(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;
}