Modular Inverse

Problem

Given a formular which result is normally very large, can’t be stored in any primitive data type. Calculate the result in mod 109+710^9+7. The formular often involve division. For example, let’s calculate this

nCr≡n!(n−r)!r!(mod109+7)nCr \equiv \frac{n!}{(n-r)!r!} \pmod {10^9+7}

Naive approach

Naive approach 1 (Heavy Implementation)

  1. Calculate n!n!, using big number class to store result
  2. Calculate (n−r)!r!(n-r)!r!, also using a custom implemented BigNumber class
    1. You can optimize this by calculate n!/r!n!/r! in one loop. This way you decimate alot of computation
  3. Divide 2 numbers to get the result
  4. Mod the result by 109+710^9+7

This requires non-trivial effort to implement BigNumber class. Python folks are in luck but most programming language doesn’t support big number by default. Assume that you are an average programmer like me. You often fail to come up with a correct implementation of the BigNumber class.

Naive approach 2 (Wrong Answer)

  1. Calculate n!(mod109+7)n! \pmod {10^9+7}
  2. Calculate (n−r)!r!(mod109+7)(n-r)!r! \pmod {10^9+7}
    1. Same as before. You can optimize this by calculate n!/r!n!/r! in one loop. This way you decimate alot of computation
  3. Divide 2 numbers to get the result

This seems natural but unfortunately gives WA, because the algorithm is wrong mathematically.

Solution

The problem with naive approach #2 is that, in step 3 where we normally divide 2 numbers, we get incorrect answer. Because division doesn’t work in modular arithmetic, only multiplication. But luckily there is a formular to address this issue, it converts division to multiplication by leveraging Modular multiplicative inverse.

Formally, if kk is a prime number, we have

a÷b≡a×b−1(modk)b−1≡bk−2(modk)a÷b≡a×bk−2(modk)\begin{align*} a \div b &\equiv a \times b^{-1} &\pmod k\\ b^{-1} &\equiv b^{k-2} &\pmod k\\ a \div b &\equiv a \times b^{k-2} &\pmod k \end{align*}

Everytime you were to do division, you multiply it with the power k−2k-2 of the divisor instead and it’s guaranteed to be correct mathematically 😎

There is a new problem araise, calculation of bk−2b^{k-2} could be expensive (for example k=109+7k=10^9+7). This could easily be solved by using a fast O(log(n))O(log(n)) power calculation algorithm

#define INF (1e9+7)
long long fastPow(int x, int p) {
	if(p == 0) return 1;
	if(p == 1) return x;
	auto k = fastPow(x,p/2);
	return k*k*fastPow(x,p%2)%INF;
}