2

Есть задача

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

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

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

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

1
  • 2
    pow(n, p, 1000000007)
    – EzikBro
    21 фев 2021 в 14:36

2 ответа 2

4

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

  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)

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

  1. аналогично можно воспользоваться формулой 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 то тут все было бы просто - малая теорема Ферма

2
  • Time limit все равно не проходит. Тот же самый тест(какой конкретно не знаю)
    – chehmakin
    21 фев 2021 в 13:53
  • @chehmakin, тогда нужна 3 оптимизация - воспользоваться формулой a^b mod c = (a mod c)^b mod c, т.е. надо пойти по логарифмическому пути - возводить в квадрат и вычислять остаток, возводить в квадрат и вычислять остаток и т.д., скорее всего если не проходит по времени, то задается высокая степень - вот ее и надо срезать таким путём
    – Zhihar
    21 фев 2021 в 13:56
3

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

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

Итоговый алгоритм имеет сложность 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))
2
  • 3
    NB: В Python есть встроенная функция pow с тремя аргументами, которая это умеет.
    – MBo
    21 фев 2021 в 16:37
  • Спасибо! Добавил в ответ. 21 фев 2021 в 16:58

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.