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

Modular Exponentiation

Compute base to the power exponent, modulo a number, with fast exponentiation.

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

  • Raise a number to a huge power in O(log exponent) steps
  • Keep every intermediate value reduced to avoid overflow
  • Handle exponent 0 and modulus 1

Условие

Показать перевод

Compute base^exponent mod modulus. The exponent can be as large as 10^18, so multiplying by base that many times is impossible; use exponentiation by squaring instead: look at the exponent's binary digits, square the base at every step, and multiply it into the result when the digit is 1. That takes about 60 steps for any exponent here.

Implement modular_exponentiation(base, exponent, modulus).

Reduce base modulo modulus first and after every multiplication. Since modulus ≤ 10^9, the product of two reduced values is below 10^18 and fits in a signed 64-bit integer.

Input

base: The base.

exponent: The power to raise the base to.

modulus: The number to take the remainder by.

Output

Return base^exponent mod modulus, a value from 0 to modulus − 1. Treat base^0 as 1 for every base, including 0, so the answer for exponent 0 is 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, and 1,594,323 = 50 × 31,886 + 23, so the answer is 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, and 1024 mod 1000 = 24.

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

Look at the exponent one binary digit at a time, starting from the lowest.

Подсказка 2

Square the base at every step and multiply it into the result when the current bit is 1.

Подсказка 3

Start the result at 1 % modulus, so modulus 1 gives 0.

Ожидаемая сложность

O(log exponent) time, O(1) extra space

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

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

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

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

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

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