I was aware of using a^(mod-2)%mod and extended euclidean for finding modular inverse. But today, while solving CNTWAYS, I came across another method for finding modular inverse. The previous two methods were too slow and apparently this method is much faster.
This is what I found in the Tester’s solution:
/* calculate all inverses of 1..8000000 mod MOD */ inv = 1; REP(i,2,800010) inv[i] = MOD - ((MOD/i)*inv[MOD%i]%MOD);
I found it interesting. So anybody has any idea how this code is actually working. Exactly what is this? I have never seen it before.