e-olymp 480. Возведение в степень — 2

Задача

Для заданных $A$, $B$ и $M$ вычислить $A^B \mod M$.

Входные данные

Во входном файле даны три натуральных числа $A$, $B$, $M$ $(1 ≤ A, \, B ≤ 10^{18}, \, 2 ≤ M ≤ 2 \cdot 10^9)$, записанные в одной строке через пробел.

Выходные данные

В выходной файл выведите одно число, равное $A^B \mod M$.

Тесты

Входные данные Выходные данные
$531$ $348$ $1645$ $911$
$1784353$ $453345$ $463973$ $214457$
$39252362$ $345673$ $786536$ $302328$
$68790234$ $679643$ $789057$ $281232$
$324$ $8564$ $45074547$ $32984424$

Код программы

Решение задачи

По свойствам операций со сравнениями по модулю:
$$C \equiv C \mod K \pmod K$$
$$CD \equiv (C \mod K) \cdot (D \mod K) \pmod K$$
$$C \equiv D \pmod K \Rightarrow C^n \equiv D^n \pmod K$$
Отсюда выводим рекуррентную формулу бинарного возведения в степень по модулю:
$$
A^B \mod M =
\begin{cases}
1 \text{ при } B = 0\\
\left ( \left (A \mod M \right ) \left ( (A \mod M)^{B-1} \mod M \right )\right )\mod M \\ \text{ при } B \equiv 1 \pmod 2\\
\left ( \left (A \mod M \right)^2 \right)^{\frac{B}{2}} \mod M \text{ при } B \equiv 0 \pmod 2 \wedge B \neq 0
\end{cases}
$$

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

One thought on “e-olymp 480. Возведение в степень — 2

Добавить комментарий