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

Задача

По трем натуральным числам [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

Код с циклом

Код с ветвлением

Решение

Для решения этой задачи я воспользовался функцией бинарного возведения в степень binpow () (рекурсивной для программы с ветвлением и нерекурсивной для программы с циклом). Это приём, позволяющий возводить любое число в [latex]n[/latex]-ую степень за [latex]O(\log n)[/latex] умножений. В этой функции при возведении я дополнительно применял операцию деление с остатком к результату res и возводимому числу a для того, чтобы получить решение.

Запустить код с циклом (ideone) можно здесь
Запустить код с ветвлением (ideone) можно здесь
Задача на E-olymp

5 thoughts on “e-olymp 273. Возведение в степень

  1. Вы изначально создаете переменные типа unsigned long long, но функция принимает значения типа long long, в данном случае ничего страшного не произойдёт, но желательно использовать один и тот же тип данных.

    • Хорошо. Правда, лаконичнее было бы вместо b = binpow (a, n/2, m); return (b * b) % m; сделать return binpow ((a * a) % m, n/2, m);
    • Хотел по троллить по return 1 % m; Однако оказалось, что Вы правы — по условию m может быть единицей. Хотя, теста такого не сделали.

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