nhant's blog

Find Modulus Inversion iteratively
By nhant, 6 years ago, In English

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?

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +17 Vote: I do not like it

The 2nd method is explained here: https://mirror.codeforces.com/blog/entry/5457?#comment-106714

Also, the mod is 1e9+7, not 1e7+7.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Updated. Thanks for the reference.

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

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 .

→ Reply