Вычислите base^exponent mod modulus. Показатель степени может достигать 10^18, поэтому умножать на base столько раз невозможно. Вместо этого используйте быстрое (бинарное) возведение в степень: идите по двоичным цифрам показателя, на каждом шаге возводите основание в квадрат и домножайте на него результат, если текущая цифра равна 1. Для любого показателя из этой задачи хватит примерно 60 шагов.
Реализуйте modular_exponentiation(base, exponent, modulus).
Сначала возьмите base по модулю modulus и делайте то же самое после каждого умножения. Так как modulus ≤ 10^9, произведение двух приведённых значений меньше 10^18 и помещается в знаковое 64-битное целое.
Входные данные
base: основание.
exponent: показатель степени.
modulus: модуль, по которому берётся остаток.
Выходные данные
Верните base^exponent mod modulus, то есть значение от 0 до modulus − 1. Считайте, что base^0 = 1 для любого основания, включая 0, поэтому при exponent = 0 ответ равен 1 mod modulus.
Ограничения
0 ≤ base ≤ 10^18
0 ≤ exponent ≤ 10^18
1 ≤ modulus ≤ 10^9
Примеры
Ввод:
base = 3
exponent = 13
modulus = 50
Ожидаемый вывод:
expected = 23
Ввод:
long long base = 3;
long long exponent = 13;
long long modulus = 50;
Ожидаемый вывод:
long long expected = 23;
Ввод:
long base = 3;
long exponent = 13;
long modulus = 50;
Ожидаемый вывод:
long expected = 23;
Пояснение
3^13 = 1 594 323, а 1 594 323 = 50 × 31 886 + 23, поэтому ответ 23.
Ввод:
base = 2
exponent = 10
modulus = 1000
Ожидаемый вывод:
expected = 24
Ввод:
long long base = 2;
long long exponent = 10;
long long modulus = 1000;
Ожидаемый вывод:
long long expected = 24;
Ввод:
long base = 2;
long exponent = 10;
long modulus = 1000;
Ожидаемый вывод:
long expected = 24;
Пояснение
2^10 = 1024, и 1024 mod 1000 = 24.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Просматривайте показатель степени по одной двоичной цифре, начиная с младшей.
Подсказка 2
На каждом шаге возводите основание в квадрат и домножайте на него результат, если текущий бит равен 1.
Подсказка 3
Начинайте с результата 1 % modulus, тогда при modulus = 1 получится 0.
Ожидаемая сложность
время O(log exponent), доп. память O(1)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.