Task
Time limit:
1000 ms,
Memory limit:
256 Mb
Возводить в степень можно гораздо быстрее, чем за n умножений! Для этого нужно воспользоваться следующими рекуррентными соотношениями:
\(a^n=(a^2)^{n/2},\ при \ четном \ n, \\ a^n=a \cdot a^{n-1},\ при \ нечетном \ n.\)
Реализуйте алгоритм быстрого возведения в степень. Если вы все сделаете правильно, то сложность вашего алгоритма будет O(logn) .
Входные данные: Вводится вещественное число a и целое число n.
Выходные данные: Выведите ответ на задачу.
Нельзя использовать стандартное возведение в степень.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2
7 |
128 |
| 2 |
1.00001
100000 |
2.71827 |
Prohibited statements:for;while;until;math;**;pow