Модуль: Быстрое возведение в степень


Задача

1 /5


Быстрое возведение в степень


Задача

Возводить в степень можно гораздо быстрее, чем за 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

 

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w64163
Python83
Комментарий учителя