Задача
По трем натуральным числам [latex]a[/latex], [latex]b[/latex] и [latex]m[/latex] вычислить значение [latex]a^b\mod m[/latex].
Входные данные
Три натуральных числа [latex]a[/latex], [latex]b[/latex], [latex]m[/latex] [latex]\left(1 \leqslant a, m \leqslant 10^9, 2 \leqslant b \leqslant 10^7\right)[/latex].
Выходные данные
Вывести [latex]a^b\mod m[/latex].
Тесты
| # | ВХОДНЫЕ ДАННЫЕ | ВЫХОДНЫЕ ДАННЫЕ |
|---|---|---|
| 1 | 1 2 100 | 1 |
| 2 | 100 2 1000000 | 10000 |
| 3 | 2 3 50 | 8 |
| 4 | 9 2 1 | 0 |
| 5 | 9 2 25 | 6 |
Код с циклом
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include <iostream> using namespace std; long binpow (long a, long n, long m) { long res = 1; while (n) { if (n & 1) { res *= a; res %= m; } a *= (a % m); a %= m; n >>= 1; } return res % m; } int main() { long a, b, m; cin >> a >> b >> m; cout << binpow (a, b, m); return 0; } |
Код с ветвлением
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include <iostream> using namespace std; long binpow (long a, long n, long m) { if (n == 0) return 1 % m; if (n % 2 == 1) return (binpow (a, n - 1, m) * a) % m; else { return binpow ((a * a) % m, n/2, m); } } int main() { long a, b, m; cin >> a >> b >> m; cout << binpow (a, b, m); return 0; } |
Решение
Для решения этой задачи я воспользовался функцией бинарного возведения в степень binpow () (рекурсивной для программы с ветвлением и нерекурсивной для программы с циклом). Это приём, позволяющий возводить любое число в [latex]n[/latex]-ую степень за [latex]O(\log n)[/latex] умножений. В этой функции при возведении я дополнительно применял операцию деление с остатком к результату res и возводимому числу a для того, чтобы получить решение.
Запустить код с циклом (ideone) можно здесь
Запустить код с ветвлением (ideone) можно здесь
Задача на E-olymp