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

by

2

Задача

Вычислить значение $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

Код

Решение

Для решения задачи создадим функцию «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

Related Images:

2 thoughts on “e-olymp 4439. Возведение в степень”

    • В тестах всегда следует проверять «опасные» случаи. Например, если используются только натуральные числа, то нужно проверить 1 в какой-то степени и что-то максимально большое, например $10^{18}$ или $100^9$.
    • В laTeX имеются хорошие средства для набора рациональных выражений вида $\frac{b}{2}$. Используйте это если понадобится.
    • Не путайте формулы с фрагментами кода. Например, $\left(a\cdot a \right)^{\frac{b}{2}}$ это формула, а pow(a*a, b/2) — код.
    • С кодом все хорошо, а в описании алгоритма ошибка.
    • В конце предложений принято ставить точку, а не точку с запятой.
    • Вы пишите, что задача требует рекурсии. Это не так. Её можно решать рекурсивно, что Вы блестяще продемонстрировали, но можно и обычным циклом:

    • В тестах всегда следует проверять «опасные» случаи. Например, если используются только натуральные числа, то нужно проверить 1 в какой-то степени.
    • Вы пишите $a^b = (a^{\frac{b}{2}})^2 = a^{\frac{b}{2}} \cdot a^{\frac{b}{2}}$. Но используете совсем другое — $a^b = \left(a^2\right)^{\frac{b}{2}}= \left(a\cdot a\right)^{\frac{b}{2}}$.

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