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.>
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.