4439. Возведение в степень
Вычислите значение xn.
Вход. Два
натуральных числа x и n.
Выход. Выведите
значение xn, если
известно что оно не превосходит 1018.
|
Пример входа |
Пример выхода |
|
2 10 |
1024 |
РЕШЕНИЕ
рекурсия
Анализ алгоритма
Как вычислить xn быстрее чем O(n)?
Например,
x10 = (x5)2 = (x
* x4)2 = (x * (x2)
2)2
Можно заметить что x2n = (x2)n, например x100 = (x2)50.
Для
нечетных степеней воспользуемся формулой x2n+1 = x
* x2n, например x11 = x
* x10.
Следующая
рекуррентная формула дает нам решение за O(log2n):
= 
При
итеративной реализации следует отдельно обработать случай x = 1, n – большое
целое число. Например при x = 1, n = 1018 для вычисления xn следует выполнить
1018 итераций,
что даст Time Limit.
Реализация алгоритма
Функция f вычисляет
значение xn.
long long
f(long long x, long long n)
{
if (n == 0) return 1;
if (n % 2 == 0) return
f(x * x, n / 2);
return x * f(x, n - 1);
}
Основная часть программы. Читаем входные данные.
scanf("%lld %lld",&x,&n);
Вычисляем и выводим ответ xn.
res = f(x,n);
printf("%lld\n",res);