在python中无聊的因子

Question

我试图理解并解决以下问题:

Sameer和Arpit想要克服他们对数学的恐惧,所以他们最近一直在练习数学问题.阿曼,他们的朋友一直在帮助他们.但事实上,Sameer和Arpit对涉及阶乘的问题感到无聊.原因是,因子在问题中太容易计算,因为它们只需要以一些素数为模的残差,并且很容易在线性时间内计算.所以为了让事情变得有趣,Aman - The Mathemagician给了他们一个有趣的任务.他给了他们一个素数P和一个接近P的整数N,并要求他们找到N!模数P.他问这样的查询.

输入:

第一行包含一个整数T,即询问的查询数.

接下来的T行包含"NP"形式的T查询.(为清晰起见)

输出:

输出正好是T行,包含N!模数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

现在我写了一个解决方案:

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

但是你可以看到这是一个效率低下的解决方案,所以我开始寻找一个更好的解决方案,而不是我知道这可以用wilson和fermet定理来解决.但是我无法理解作者试图说的是什么他说:

**在数论中,威尔逊定理指出自然数n> 1是素数,当且仅当

现在我们可以写:

(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

**

所以我实现了这个:

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

但是从我得到的输出中我认为我误解了他所写的内容.可以有人告诉我他告诉我要计算什么,以及如何编写他所说的代码.

Answer 1

这不是威尔逊定理的直接应用.与它一起使用以下事实:

• 如果n >= p那么n! = 0 (mod p)
• 如果n < p再n! = (p-1)!/[(n+1)(n+2)..(p-1)].现在使用这个事实(p-1)! = -1 (mod p).剩下的就是模块乘法逆(例如使用扩展欧几里德算法)的数字n+1, n+2, ... , p-1,这个数最多1000来自于这个数字abs(n-p) <= 1000.乘(p-1)! = -1 (mod p)用数字的所有模反元素n+1, n+2, ... , p-1,你会得到答案.(正如约翰科尔曼所指出的那样,你也可以对产品进行反转,而不是优化反转的乘积)

在你的情况下n=2, p=5(只是为了看它是如何工作的)

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)