我试图编写一个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新手,希望有人能帮我找出代码中的时间瓶颈。是读取输入和打印输出还是计算本身?谢谢你的帮助
从效率的角度来看,我不认为你的代码有什么问题,它只是不必要的复杂
这就是我所说的直截了当的解决方案:
PyPy3确实接受了这一点,但CPython3却不接受。而Py3仍然需要0.93秒
我认为他们的时间限制不适合Python。但是如果你还没有用Py3试试你的
如果有人想知道
map
是否浪费时间,以下内容在0.92秒内被接受:相关问题 更多 >
编程相关推荐