Как ускорить работу программы

Question

Есть задача

Возвести число в степень и вывести остаток от деления результата на 1000000007

У меня такой код

n, p = input().split()
n = int(n)
p = int(p)
print((n ** p) % 1000000007)

На одном из тестов выдает Time limit. Как я могу оптимизировать код?

Answer 1

тут надо применить арифметику остатков

воспользоваться формулой a^b mod c = (a mod c)^b mod c

что это дает - не надо работать с чрезмерно большими основаниями

сравните скорость работы этих двух кодов:

n = 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 #int(n)
p = 111111
z = 1000000007

x = n % z

print((x**p) % z)
print((n**p) % z)

скорость отличается на порядок

аналогично можно воспользоваться формулой a^b mod c = a^(b mod c - 1) mod c

в итоге код будет таким:

x = n % z
y = p % (z - 1)

print(x**p % z)

если я не путаю конечно с п.2)

P.S.

1000000007 - простое число, но вроде в этой задаче этот факт никак не использовать

вот если бы надо было найти остаток от деления n^1000000007 на 1000000007 то тут все было бы просто - малая теорема Ферма

Answer 2

Возведение в степень по модулю - хорошо исследованная задача. Главная идея - после каждой арифметической операции брать результат по модулю. Тем самым арифметика работает с операндами ограниченной длины, то есть быстрее.

Вторая вещь которая ускоряет получение результата - быстрое возведение в степень.

Итоговый алгоритм имеет сложность O(log(p)), p - показатель степени. От основания степени время работы не зависит (почти, всё-таки основание надо прочитать и взять от него модуль). На практике это означает что степень считается быстрее чем производится считывание чисел из входного потока.

def mod_mul(mod, a, b):
    return (a * b) % mod


def mod_pow(mod, a, b):
    if b == 0:
        return 1
    if b == 1:
        return a
    if b % 2 == 0:
        p2 = mod_pow(mod, a, b // 2)
        return mod_mul(mod, p2, p2)
    return mod_mul(mod, a, mod_pow(mod, a, b - 1))


mod = 1000000007
n, p = map(int, input().split())
print(mod_pow(mod, n % mod, p))

$ echo 1234567 115792089237316195423570985008687907853269984665640564039457584007913129639935 | python exponentiation-by-squaring.py
630926649

И как мне подсказали в комментарии, всё уже придумано до нас. В Python есть встроенная реализация модулярной экспоненты - pow:

n, p = map(int, input().split())
print(pow(n, p, 1000000007))

БЛОГ НА HUSL

Как ускорить работу программы

Ответы (2 шт):