Raising to a power is faster than n multiplications! To do this, use the following recurrence relations:
\(a^n=(a^2)^{n/2},\ for \ even \ n, \\ a^n=a \cdot a^{n-1 },\ for \ odd \ n.\)
Implement the fast exponentiation algorithm. If you do everything right, then the complexity of your algorithm will be O(logn) .
Input
The program receives a real number a and an integer n as input. Each number on a separate line.
Imprint
Output
\(a^n\).
Examples
| # |
Input |
Output |
| 1 |
2
7 |
128 |
| 2 |
1.00001
100000 |
2.71827 |
Запрещенные операторы:for;while;until;math;**;pow