python中的无聊阶乘 [英] Boring Factorials in python

问题描述

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

I am trying to understand and solve the following problem :

Sameer和Arpit想要克服他们的问题由于担心数学，因此他们最近经常练习数学问题。阿曼，他们的朋友
一直在帮助他们。但是，顺便说一句，萨默和阿皮特已经厌倦了涉及阶乘的问题。原因是，阶乘
太容易计算出问题，因为它们只需要对余数
进行模数质数运算，并且很容易在线性时间内计算。因此，为了使
变得有趣，Aman-The Mathemagician给了
一个有趣的任务。他给他们一个质数P和一个接近P的整数N
，并要求他们找到N！

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，即所查询的数量。

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

接下来的T行包含 NP形式的T个查询。 （报价中
的清晰度）

Next T lines contains T queries of the form "N P". (quotes for clarity)

输出：

准确输出T线，含N！

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:

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

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

**

所以我实现了这一点：

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.

推荐答案

这不是威尔逊定理的直接应用。连同它一起使用以下事实：

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

• 如果 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 + 1，.。 。，p-1 ，该数字最多为 1000 ，原因是 abs（np）<= 1000 。乘以（p-1）！ = -1（mod p），其中所有模块的乘积逆数均 n + 1，n + 2，...，p-1 然后您得到答案。 （正如约翰·科尔曼指出的那样，您也可以对乘积进行逆运算而不是对逆积进行优化）

• 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)

您的案例 n = 2，p = 5 （只是看它如何工作）

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)

这篇关于python中的无聊阶乘的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！