Задача
Вычислить значение $a^b$.
Входные данные
Два натуральных числа $a$ и $b$.
Выходные данные
Выведите значение $a^b$, если известно что оно не превосходит $10^{18}$.
Тесты
| № | ВХОДНЫЕ ДАННЫЕ | ВЫХОДНЫЕ ДАННЫЕ |
| 1 | 1 100 | 1 |
| 2 | 2 10 | 1024 |
| 3 | 3 7 | 2187 |
| 4 | 8 9 | 134217728 |
| 5 | 10 10 | 10000000000 |
| 6 | 100 9 | 1000000000000000000 |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
class Main{ public static long pow(long a, long b){ if(b == 0){ return 1; } if(b % 2 == 0){ return pow(a * a, b / 2); } return a * pow(a, b - 1); } public static void main (String[] args){ java.util.Scanner in = new java.util.Scanner(System.in); long a = in.nextLong(), b = in.nextLong(); System.out.println(pow(a,b)); } } |
Решение
Для решения задачи создадим функцию «pow()», заметим, что для любого числа $a$ и чётного числа $b$ выполнимо очевидное тождество (следующее из ассоциативности операции умножения):
$$a^b = \left(a^2\right)^{\frac{b}{2}}= \left(a\cdot a\right)^{\frac{b}{2}}$$
Оно и является основным в методе бинарного возведения в степень. Действительно, для чётного $b$ мы показали, как, потратив всего одну операцию умножения, можно свести задачу к вдвое меньшей степени.
Осталось понять, что делать, если степень b нечётна. Здесь мы поступаем очень просто: перейдём к степени b-1, которая будет уже чётной:
$$a^b = a^{b-1} \cdot a$$
Итак, мы фактически нашли рекуррентную формулу: от степени $b$ мы переходим, если она чётна, к $\frac{b}{2}$, а иначе — к $b-1$.
Примечание
Задача требует использование быстрого алгоритма, так как прямое умножение $b$ раз для возведение в $b$-ю слишком медленно, из-за большого количества перемножений. Алгоритм быстрого возведения в степень — это предназначенный для возведения числа в натуральную степень за меньшее число умножений, чем это требуется в определении степени.
Ссылки
Условие задачи на e-olymp
Код на Ideone
Засчитанное решение на e-olymp