Last Updated: 17 Jun, 2021

Fermat Little Theorem

Moderate

Asked in company

Solve now

Problem statement

You are given two integers 'n' and 'r' and a prime number 'p'. Your task is to find (nCr) % p where nCr can be calculated as n! / (r! * (n - r)!).

Note :

N!  =  1 * 2 * 3 *... N

Input format :

The first line of input contains a single integer 'T', representing the number of test cases. 

The first line of each test case contains three space-separated integers 'n', 'r', and 'p'.

Output format :

For each test case, print a single line containing an integer representing the value of (nCr) % p.

The output of each test case will be printed on a separate line.

Note:

You don't need to input or print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 5 
1 <= n, r, p <= 5 * 10 ^ 2
p is prime number.

Time limit: 1 sec.

Solve now

Approaches

01 Approach

Expression nCr = fact(n) / (fact(r) * fact(n - r))

Here fact() means factorial.

nCr % p = (fac[n] * powInverse(fac[r], 1) % p * powInverse(fac[n - r], 1) % p) % p; (From Fermat Little Algorithm) which will further be broken down to

nCr % p = (fac[n] % p * pow(fac[r], p - 2) % p * pow(fac[n - r]), p - 2) % p

Here powInverse() means inverse modulo under p i.e (1 / n) % p and pow() means power under modulo p.

To calculate the factorial we can maintain a dp array such that dp[X] = dp[X - 1] * X as X! = (X) * (X - 1)!. Where ‘X’ is some integer. And the factorial of the required number can be found at the last index of dp array.

Algorithm :

Make a function, say ‘powInverse’ which will calculate us (X ^ (-1)) modulo ‘p’ taking arguments ‘n’ and ‘p’.
Make a function, say ‘pow’ which will calculate the power of a number modulo ‘p’ taking arguments ‘x’ for which the power is to be calculated, ‘y’ denoting power, and ‘p’.
If (n < r) return 0, as nCr for n < r is 0.
If r = 0, then return 1.
Make a dp array say ‘dp[]’ of length ‘n + 1’ to store the factorial of the number modulo p.
Make dp[0] = 1 as Factorial of 0 is 1.
Iterate from ‘i’ = 1 till ‘i’ = N
- Store dp[i] = (dp[i - 1] * i) % p.
Return (dp[n] * powInverse(dp[r], p) % p * powInverse(dp[n - r], p) % p) % p to the given function.

Description of ‘pow’ function:

Function to calculate (x ^ y) % p.

First, initialize a variable ‘ans’ which will store the power of the number modulo ‘p’ and initialize it to 1.
Update ‘x’ as x = x % p if ‘x’ is more than or equal to ‘p’.
Make an iteration for ‘y’ until it is a positive integer.
- Check if ‘y’ is odd, if odd then:
  - Multiply ‘x’ with the ‘ans’ and modulo the result obtained and store it in ‘ans’.
  - Do modular squaring of 'x' i.e. do 'x' = ('x' * 'x') % 'p'.
Return ‘ans’ to the function ‘pow’.

Description of ‘powInverse’ function:

The function will find inverse modulo of 'n' under ‘p’, i.e. (1 / n ) % p.

Return the function ‘pow (n, p - 2, p)’

Solve now