Вычисление a ^ b mod p для большого простого числа p - PullRequest
Новая
       117

Вычисление a ^ b mod p для большого простого числа p

0 голосов
/ 07 августа 2020

Я пытаюсь написать код python, который вычисляет a ^ b mod p, где p = 10 ^ 9 + 7 для списка пар (a, b). Проблема в том, что код должен завершить sh вычисление и вывести результат менее чем за 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 и надеялся, что кто-то может помочь мне определить время bottle шеи в моем коде. Считывает ввод и вывод на печать или сам расчет? Спасибо за помощь!

1 Ответ

0 голосов
/ 07 августа 2020

Я не вижу чего-то неправильного в вашем коде с точки зрения эффективности, это просто излишне сложно.

Вот то, что я бы назвал прямым решением: 

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