Все задачи
Средне Решено: 0 Процент решений: 0%

Возведение в степень по модулю

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

Чему вы научитесь

  • Возводить число в огромную степень за O(log exponent) шагов
  • Приводить по модулю каждое промежуточное значение, чтобы избежать переполнения
  • Обрабатывать exponent = 0 и modulus = 1

Условие

Вычислите 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

Примеры

Пример 1
Ввод:
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.

Пример 2
Ввод:
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. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

Пока нет опубликованных решений. Решите задание, чтобы поделиться первым.