New Method For Finding Modular Inverse

algorithm
modular
number-theory

#1

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] = 1; REP(i,2,800010) inv* = 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.


#2

There are three common ways of computing modular inverses.
They have all been explained here: http://e-maxx.ru/algo/reverse_element
It’s a Russian website, so translate it to English, if needed.


#3

vai ami o kisu bujlam na. onek time pass korlam but still don’t know how it works. @forthright


#4

Thank you. I was looking for the proof.