SPOJ PROBLEM 16211: BORING FACTORIALS

Problem Link: http://www.spoj.com/problems/DCEPC11B/


SUMMARY
Given two number n and p. Your task is to print answer i.e equal to n!%p

Logic
Wilson’s Theorem 

In number theory, Wilson's theorem states that a natural number n > 1 is a prime number if and only if

.

 Now from this we can write:
(p-1)!   ≡  -1 (mod p)
1*2*3*.........*(n-1)*(n)*..............*(p-1)  ≡   -1 (mod p)
n!*(n+1)*...........*(p-1)   ≡   -1 (mod p)
n!  ≡    -1*[(n+1)*...............(p-2)*(p-1)]^-1 (mod p)

let a=[(n+1)*...............(p-2)*(p-1)]

so

n!≡-1*a^-1(mod p)

From Fermat's Theorem:

a^(p-1) ≡ 1(mod p)

multiply both side by a^-1

a^(p-2)  ≡ a^-1(mod p)

now simply we have to find a^(p-2) mod p

To View My Solution:

https://github.com/shivam04/spoj/blob/master/DCEPC11B