**Note**: I couldn't find exact terminology for this question. It is something like "Russian Peasant multiplication" for calculating exponent.

There's a well-known way of calculating $$$p^k$$$ as follow:

```
template<typename T> T pow(T p, int k) {
T t = 1;
while (k > 0) {
if (k % 2 == 1) t = t * p;
p = p * p;
k /= 2;
}
return t;
}
```

We can reduce one multiplication ($$$1 * p$$$) from above implementation with a variable named `first_mul`

:

```
template<typename T> T pow(T p, int k) {
T t;
bool first_mul = false;
while (k > 0) {
if (k % 2 == 1) {
if (!first_mul) t = p, first_mul = true;
else t = t * p;
}
p = p * p;
k /= 2;
}
return t;
}
```

I found that when operator $$$*$$$ is very heavy, like matrix or polynomial multiplication, this trick reduces runtime a lot.

So I want to ask:

1. Is there a simple algorithm that is better than above algorithm for $$$k \leq 10^9, k \leq 10^{18}$$$, $$$k \leq 10^{100}$$$?

2. Is there any way to find the optimal number of multiplications in calculating $$$p^k$$$?

If you know that k>=1, you can set t = p; and decrease k by 1 instead of strange if

From wiki: