Contest Hello 2019 problem D requires calculating modulo inverse mod (1e9 + 7). I understood the proof to the extended euclidean recursive algorithm. But I can't prove the correctness of these 2 algorithms:
// Iterative: tourist, dotorya
const int md = (int) 1e9 + 7;
int inv(int a) {
a %= md;
if (a < 0) a += md;
int b = md, u = 0, v = 1;
while (a) {
int q = b / a;
b -= q * a; swap(a, b);
u -= q * v; swap(u, v);
}
assert(b == 1); // also why assert here?
if (u < 0) u += md;
return u;
}
// lych_cys, Petr, djq_cpp, stO
const int md = (int) 1e9 + 7;
vector<int> inv(100, 0);
inv[0] = inv[1] = 1;
for (int i = 2; i < 100; i++) {
inv[i] = (md - 1LL * inv[md % i] * (md / i) % md) % md;
}
Can someone help me prove them?
The 2nd method is explained here: https://codeforces.net/blog/entry/5457?#comment-106714
Also, the mod is 1e9+7, not 1e7+7.
Updated. Thanks for the reference.
The first one is a modified implementation of Extended Euclidean algorithm. You may check this link and get more information.
You know the process of Euclidean algorithm to calculate
could be represented as a sequence r1, r2, ..., rm - 1, rm, where r1 = x, r2 = y, 
, and consequently 
, rm = 0.
The process of Extended Euclidean algorithm to calculate
could also be represented as (u1, v1, r1), (u2, v2, r2), ..., (um - 1, vm - 1, rm - 1), (um, vm, rm), where ri is defined as above, and besides, uix + viy = ri is satisfied.
If
, then vm - 1 is the modular multiplicative inverse of y with respect to the modulus x, or the inverse does not exist otherwise. But how to get vm - 1? we can simply assign that u1 = v2 = 1, v1 = u2 = 0, but what are the following? Noticing 
, if we substract 
times the (i + 1)-th equation from the i-th equation, we can get the (i + 2)-th equation. That yields an iterative implementation.
The first one you mentioned only keeps (vi, ri) and checks if
.