(см. объяснение)
Объяснение:
Решая задачу "в лоб", нам потребовалось бы умножить число само на себя ровно 147 раз. Это много, потому попробуем оптимизировать алгоритм. Заметим, что 
, а 
. Изначально имеем число 
. Пусть 
- степень. Пусть 
- наш будущий ответ. На каждой итерации цикла будем умножать сам на себя, а 
целочисленно делить на 2. При этом заметим, что когда 
, то нам надо умножить текущий результат 
на . Таким образом, всего за 8 итераций (вместо 147!) мы можем возвести некоторое число в степень 147.
Покажем, как написать это на C++:
#define ll long long
ll bpow(ll x, ll y) {
ll r = 1;
while (y > 0) {
if (y % 2 > 0) {
r *= x;
}
x *= x;
y /= 2;
}
return r;
}
Задание выполнено!
