python - python 中无聊的阶乘

Question

我正在尝试理解并解决以下问题:

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.

输入:

第一行包含一个整数 T，表示询问的数量。

接下来的 T 行包含 T 个形式为“N P”的查询。 (报价为 清晰度)

输出:

正好输出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

但如您所见，这是一个低效的解决方案，所以我开始寻找比我知道可以使用威尔逊和费米特定理解决这个问题更好的解决方案。但我无法理解作者想说的是什么 他说:

**在数论中，威尔逊定理指出自然数 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) 的事实.剩下的就是modular multiplicative inverse。 (例如使用 extended Euclidean algorithm)的数字 n+1, n+2, ... , p-1哪个数最多为1000从事实上abs(n-p) <= 1000 .相乘(p-1)! = -1 (mod p)与数字的所有模乘逆n+1, n+2, ... , p-1你得到了答案。 (正如 John Coleman 指出的那样，您也可以对乘积进行逆运算而不是逆运算的乘积作为优化)

在你的情况下 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)