john smith - 6 months ago 16x

Python Question

I am trying to understand and solve the following problem :

Sameer and Arpit want to overcome their fear of Maths and so they have been recently practicing Maths problems a lot. Aman, their friend

has been helping them out. But as it goes, Sameer and Arpit have got

bored of problems involving factorials. Reason being, the factorials

are too easy to calculate in problems as they only require the residue

modulo some prime and that is easy to calculate in linear time. So to

make things interesting for them, Aman - The Mathemagician, gives them

an interesting task. He gives them a prime number P and an integer N

close to P, and asks them to find N! modulo P. He asks T such queries.

Input :

First line contains an integer T, the number of queries asked.

Next T lines contains T queries of the form “N P”. (quotes for

clarity)

Output:

Output exactly T lines, containing N! modulo P.

`Example`

Input:

3

2 5

5 11

21 71

Output:

2

10

6

Constraints:

1 <= T <= 1000

1 < P <= 2*10^9

1 <= N <= 2*10^9

Abs(N-P) <= 1000

now to this I wrote a solution :

`def factorial(c):`

n1=1

n2=2

num=1

while num!=c:

n1=(n1)*(n2)

n2+=1

num+=1

return n1

for i in range(int(raw_input())):

n,p=map(int,raw_input().split())

print factorial(n)%p

but as you can see this is inefficient solution so I started searching for a better solution than I came to know that this can be solved using wilson's and fermet's theorem.But I am unable to understand what the author is trying to say

He says:

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

**

so I implemented this:

`def factorial1(n,p): # to calculate a=[(n+1)*...............(p-2)*(p-1)]`

n0=n+1

n1=n0+1

while n1<=(p-1):

n0=n1*n0

n1+=1

return n0

# print nf(2,5)

for i in range(10):

n,p=map(int,raw_input().split())

if n>p:

print 0

elif n==p-1:

print p-1

else:

print (factorial1(n,p)**(p-2))%p #a^(p-2) mod p

But from the output which I am getting I think I misunderstood what he wrote .Can someone tell me what is he telling me to calculate and how do I write the code for what he is saying.

Answer

This is not a straight-forward application of the Wilson's theorem. Along with it use the following facts:

- if
`n >= p`

then`n! = 0 (mod p)`

- if
`n < p`

then`n! = (p-1)!/[(n+1)(n+2)..(p-1)]`

. Now use the fact that`(p-1)! = -1 (mod p)`

. All that is left for you to find is the modular multiplicative inverse (using extended Euclidean algorithm for example) of the numbers`n+1, n+2, ... , p-1`

which number is at most`1000`

from the fact that`abs(n-p) <= 1000`

. Multiply`(p-1)! = -1 (mod p)`

with all modular multiplicative inverse of the numbers`n+1, n+2, ... , p-1`

and you get the answer. (as John Coleman pointed out you could also do a inverse of the the product and not product of the inverse as an optimization)

In your case `n=2, p=5`

(just to see how it works)

```
n! = 2! = 4!/(3*4) = (-1)*2*4 = 2 (mod 5)
# 2 is modular inverse of 3 since 2*3 = 1 (mod 5)
# 4 is modular inverse of 4 since 4*4 = 1 (mod 5)
```

Source (Stackoverflow)

Comments