Задача
Для заданных $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$ |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <iostream> #include #include using namespace std; long long modPow(long long base, long long exponent, long long mod){ base %= mod; long long pow; if(exponent == 0){ pow = 1; } else if(exponent % 2 == 0){ pow = modPow(base * base, exponent / 2, mod) % mod; } else{ pow = (base * modPow(base, exponent - 1, mod)) % mod; } return pow; } int main(){ long long a, b, m; cin >> a >> b >> m; cout << modPow(a, b, m); return 0; } |
Решение задачи
По свойствам операций со сравнениями по модулю:
$$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