extended gcd

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
int ext_gcd(int a, int b, int &x, int &y) {
if(a == 0) {
x = 0, y = 1;
return b;
}
int _x, _y;
int g = ext_gcd(b % a, a, _x, _y);
// (b % a) * _x + a * _y = g
// (b - (b/a) * a) * _x + a * _y = g
// a * (_y - (b / a) * _x) + b * _x = g
x = _y - (b / a) * _x;
y = _x;
return g;
}