Задача
Для заданных $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 |
import java.util.Scanner; public class Main { public static long binPow(long a, long b, int m) { a %= m; if (b == 0) return 1; else if (b % 2 == 0) { return binPow((a * a) % m, b / 2, m); } else return (a * binPow(a, b - 1, m)) % m; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); long a = scanner.nextLong(); long b = scanner.nextLong(); int m = scanner.nextInt(); System.out.println(binPow(a, b, m)); } } |
Решение задачи
По свойствам операций со сравнениями по модулю:
$$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