inline int inv(int a, int m) {
a %= m;
if (a < 0) a += m;
int b = m, u = 0, v = 1;
while (a) {
int t = b / a;
ux++;
b -= t * a; swap(a, b);
u -= t * v; swap(u, v);
}
assert(b == 1);
if (u < 0) u += m;
return u;
}
I bumped into this while reading tourist's code for today's Atcoder's F. It finds the inverse of a modulo m if it exists. All I could understand is that, b has to be 1 in the end for the inverse to exist. Could anyone help me understand this code?
TIA.
This is just another implementation of Extended Euclid Algorithm.
Thanks!