fattoriali Boring in pitone

Question

che sto cercando di capire e risolvere il seguente problema:

Sameer e Arpit vogliono superare la loro paura della matematica e così sono state recentemente praticato problemi di matematica un sacco. Aman, il loro amico li sta aiutando. Ma allo stesso modo, Sameer e Arpit hanno annoiato di problemi che coinvolgono fattoriali. Essendo il motivo, i fattoriali sono troppo facili da calcolare nei problemi in quanto richiedono solo il residuo modulo alcuni primi e che è facile da calcolare in tempo lineare. Quindi per rendere le cose interessanti per loro, Aman - The Mathemagician, dà loro un compito interessante. Dà loro un numero primo P e un numero intero N vicino a P, e chiede loro di trovare N! modulo P. Chiede a T tali domande.

ingresso:

prima riga contiene un intero T, il numero di query chiesto.

Le righe T successive contengono richieste T della forma "N P". (preventivi per chiarezza)

uscita:

uscita esattamente linee T, contenente 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 

ora a questo ho scritto una soluzione:

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 

ma come si può vedere si tratta di una soluzione inefficiente così ho iniziato la ricerca di una soluzione migliore rispetto sono venuto a sapere che questo può essere risolto usando il teorema di wilson e fermet.Ma non riesco a capire cosa l'autore sta cercando di dire Egli dice:

** Nella teoria dei numeri, il teorema di Wilson afferma che un numero naturale n> 1 è un numero primo se e solo se

Ora da questo possiamo scrivere:

(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 

**

così ho implementato questo:

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 

Ma dall'uscita che sto ottenendo penso di aver frainteso quello che ha scritto. Può qualcuno mi dice cosa mi sta dicendo di calcolare e come scrivo il codice per quello che sta dicendo.

Answer 1

Questa non è un'applicazione diretta del teorema di Wilson.Insieme con esso uso i seguenti fatti:

• se n >= p poi n! = 0 (mod p)
• se n < p poi n! = (p-1)!/[(n+1)(n+2)..(p-1)]. Ora usa il fatto che (p-1)! = -1 (mod p). Tutto quello che ti resta da trovare è il modular multiplicative inverse (usando extended Euclidean algorithm per esempio) dei numeri n+1, n+2, ... , p-1 il cui numero è al massimo 1000 dal fatto che abs(n-p) <= 1000. Moltiplicare (p-1)! = -1 (mod p) con tutti i moltiplicativi modulari inversi dei numeri n+1, n+2, ... , p-1 e si ottiene la risposta. (Come John Coleman ha sottolineato che si potrebbe anche fare un inverso del prodotto del prodotto e non di l'inverso come un'ottimizzazione)

Nel tuo caso n=2, p=5 (solo per vedere come funziona)

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) 

Answer 2

dopo aver lottato per lunghe ore sono riuscito a ottenere questa soluzione e questo dà risultati corretti entro il limite di tempo. Stavo calcolando la stessa cosa nel mio codice nella domanda tranne l'ultima riga in questo codice (cioè) sottraendo la risposta da p

for i in range(int(raw_input())): 
    n,p=map(int,raw_input().split()) 
    if n>=p: 
     print 0%p 
    elif n==p-1: 
     print p-1 
    else: 
     n0=n+1 
     n1=n0+1 
     while n1<=(p-1): 
      n0=n1%p*n0%p 
      n1+=1 
     print p-pow(n0,(p-2),p)