Modular Multiplicative Inverse Concepts

Summary

Given a modular MOD, if we want to calculate the division of two integers, we could use the technique Modular Multiplicative Inverse.

a / b = a * b_ % MOD => b * b_ % mod = 1

To calculate b_, we could use Fermat’s little theorem. If mod is a prime number, we have

b^mod % mod = b => b^(mod-1) % mod = 1 => b^(mod-1) = b * b_ => b_ = b^(mod-2) % mod

If we use Binary Exponentiation technique, we could calculate b_ efficiently.

auto b_ = power(b, mod - 2, mod);
ll power(ll base, int i, int mod) {
      if (i == 0) {
          return 1;
      } else if (i == 1) {
          return base;
      } else if ((i & 1) == 0) {
          return power((base * base) % mod, i / 2, mod);
      } else {
          return (base * power((base * base) % mod, (i - 1) / 2, mod)) % mod;
      }
  }