计算大素数p的a^b mod p

2024-03-29 14:43:13 发布

您现在位置:Python中文网/ 问答频道 /正文

我试图编写一个python代码来计算a^b mod p,其中p=10^9+7表示一组对(a,b)。挑战在于代码必须完成计算并将结果输出到<;1秒。我已经实现了连续平方运算来快速计算a^b mod p。请参阅下面我的代码:

from sys import stdin, stdout
rl = stdin.readline
wo = stdout.write
m = 10**9+7
def fn(a,n):
    t = 1
    while n > 0:
        if n%2 != 0: #exponent is odd
            t = t*a %m
        a = a*a %m
        n = int(n/2)
    return t%m

t = int(rl()) # number of pairs
I = stdin.read().split() # reading all pairs
I = list(map(int,I)) # making pairs a list of integers
# calculating a^b mod p. I used map because I read its faster than a for loop
s = list(map(fn,I[0:2*t:2],I[1:2*t:2])) 
stdout.write('\n'.join(map(str,s))) # printing output

对于200000对(a,b)和a,b<;10^9,我的代码采用>;1秒。我是python新手,希望有人能帮我找出代码中的时间瓶颈。是读取输入和打印输出还是计算本身?谢谢你的帮助


Tags: of代码ltmodmapreadstdinstdout
1条回答
网友
1楼 · 发布于 2024-03-29 14:43:13

从效率的角度来看,我不认为你的代码有什么问题,它只是不必要的复杂

这就是我所说的直截了当的解决方案:

n = int(input())
for _ in range(n):
    a, b = map(int, input().split())
    print(pow(a, b, 10**9 + 7))

PyPy3确实接受了这一点,但CPython3却不接受。而Py3仍然需要0.93秒

我认为他们的时间限制不适合Python。但是如果你还没有用Py3试试你的

如果有人想知道map是否浪费时间,以下内容在0.92秒内被接受:

n = int(input())
for _ in range(n):
    a, b = input().split()
    print(pow(int(a), int(b), 10**9 + 7))

相关问题 更多 >