Быстрое возведение в степень
Задача
Возводить в степень можно гораздо быстрее, чем за n умножений! Для этого нужно воспользоваться следующими рекуррентными соотношениями:
\(a^n=(a^2)^{n/2}\) при четном n
,
\(a^n=a \cdot a^{n-1}\) при нечетном n.
Реализуйте алгоритм быстрого возведения в степень. Если вы все сделаете правильно, то сложность вашего алгоритма будет O(logn)
.
Входные данные
Вводится вещественное число a
и целое число n
.
Выходные данные
Выведите ответ на задачу, с точностью 6 знаков после запятой.
Нельзя использовать стандартное возведение в степень.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
2
7 |
128 |
2 |
1.00001
100000
|
2.71827 |
Запрещенные операторы: pow
; **
; log