Задача · Алгоритмы и сложность · урок 9 из 9
Задача: быстрое возведение в степень
Напишите функцию long long power(long long base, int exp), которая возвращает base в степени exp. Число умножений должно расти как O(log exp), а не как O(exp). Для чётного показателя power(b, 2 * k) равно p * p, где p — значение power(b, k).
power(2, 10)→1024power(3, 13)→1594323power(-2, 5)→-32
Ограничения: exp не меньше 0, а любое число в степени 0 равно 1. Основание может быть отрицательным, а результат всегда помещается в long long.
