I noticed Petr uses modular inverse a lot when doing problems that have solutions mod some prime. I was wondering what he uses them for and why they are useful. Most of the time I read his code and follow it up until he starts using mod Inv and then I'm lost. Anyone care to explain?
Imagine you want to calculate a/b mod p,where a divides b, and b is prime to p, i.e gcd(b,p)=1,then: (a/b)mod p=a*inv(b,p) mod p.So you get ride of dividing! this is most useful when a and b are really big numbers. for example when you want to find n!/k! mod a prime number p,when k<p.you can easily solve this even when n and k are of order of million.>
Wow thank you, there have been many times where I wanted to divide under modulus but couldn't! This will definitely come in handy for future competitions.
If the modulus is not prime, the existence of the inverse is not guaranteed, at least as far as my understanding of math goes. Fortunately, 99% of competition tasks provide prime moduli, so that shouldn't be too much of a problem.
