modulo calculate

general
,
1

how to calculate (!a/!b)mod N

2

read here - http://discuss.codechef.com/questions/3869/best-known-algos-for-calculating-ncr-m/3876

1 Like
3

thanks…

4

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: http://en.wikipedia.org/wiki/Modular_multiplicative_inverse

1 Like