how to calculate (!a/!b)mod N
read here - Best known algos for calculating nCr % M - #2 by gamabunta - tutorial - CodeChef Discuss
1 Like
thanks…
Let a! = x, b! = y. Then you want to calculate x/y (mod N) which can be obtained as x*z (mod N) where z is the modular multiplicative inverse of y, which exists if and only if y and N are prime to each other. If N is a prime number, then for all y in the set of natural numbers, y and N will be prime to each other.
You can calculate modular multiplicative inverse using several ways including Extended Euclidean Algorithm, Fermat’s Little Theorem, etc.
More read: Modular multiplicative inverse - Wikipedia
1 Like