Need help in understanding a different code for inverse modulo

Правка en3, от sinus_070, 2017-09-30 18:04:13
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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский sinus_070 2017-09-30 18:04:13 11 Tiny change: 'to be $1$ for the i' -> 'to be $1$ in the end for the i'
en2 Английский sinus_070 2017-09-30 17:37:14 76 Tiny change: 'has to be 1 for the i' -> 'has to be $1$ for the i'
en1 Английский sinus_070 2017-09-30 17:35:40 515 Initial revision (published)