Exponenciação rápida
Problem
Elevar a uma potência é muito mais rápido do que n multiplicações! Para fazer isso, use as seguintes relações de recorrência:
\(a^n=(a^2)^{n/2}\) even n,
\(a^n=a \cdot a^{n-1}\) para ímpar n.
Implemente o algoritmo de exponenciação rápida. Se você fizer tudo certo, a complexidade do seu algoritmo será O(logn) .
Entrada
Insira um número real a e um número inteiro n.
Impressão
Imprima a resposta do problema, com precisão de 6 casas decimais.
Você não pode usar a exponenciação padrão.
Exemplos
| # |
Entrada |
Saída |
| 1 |
2
7 |
128 |
| 2 |
1.00001
100000
|
2.71827 |
Запрещенные операторы: pow; **; log