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

Question

我正在尝试编写计算 a^b mod p 的 python 代码，其中 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 的新手，希望有人能帮助我确定代码中的时间瓶颈。是读取输入和打印输出还是计算本身？感谢您的帮助！

Answer 1

从效率的角度来看，我没有看到您的代码有什么问题，它只是不必要地复杂。

我称之为 straight-forward 解决方案：

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

这确实被 PyPy3 接受了，但没有被 CPython3 接受。而使用 PyPy3 仍然需要 0.93 秒。

我会说他们的时间限制不适合 Python。但是，如果您还没有使用 PyPy3，请尝试一下。

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

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

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

Calculating a^b mod p for a large prime p

python

performance

exponentiation

mod