Где применяется
1. Задача
Шаг 135 искал простые числа и тратил меньше работы на каждое число. Здесь мы тратим меньше работы на каждую степень. Нужно посчитать base^exp: основание base, умноженное само на себя exp раз. Когда exp маленькое, можно просто умножать. Когда exp равно миллиону или миллиарду, умножение по одному шагу означает миллион или миллиард операций.
Есть и вторая проблема. У числа 21000000 больше 300 000 цифр. Обычное целое столько не вмещает, да такое число обычно и не нужно: задача просит ответ по модулю некоторого числа m, то есть остаток от деления на m. Значит, нужно посчитать base^exp mod m так, чтобы промежуточные числа оставались маленькими, а шагов было намного меньше, чем exp.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи, где число возводят в огромную степень, часто с остатком. Возведение основания в квадрат и деление степени пополам дают O(log n) шагов там, где простое умножение даёт n. Когда модуль около 10^9, квадраты превышают 2^53, и как с этим быть, показывает урок 137.
Быстрое возведение дробного числа без остатка. Для отрицательного n возводи 1/x в степень минус n.
Модуль 1337, так что квадраты далеко от 2^53. Иди по цифрам b, возводи текущий результат в 10-ю степень и умножай на a в степени следующей цифры.
Каждая проверка это два вызова powMod, а внешний модуль не больше 1000, так что версия из урока безопасна.