Hide

# Problem DDon't Be Such a Square

Let’s say you have a number x and want to write a program to find out the value of $x^ n$ (and that you can’t use any math functions available in your programming language of choice). By definition, $x^ n$ is $x$ multiplied by itself $n$ times, so this program would actually be fairly simple:

a = 1
i = 0
while i < n do
a = a * x
i = i + 1
end while


However, like most simple algorithms, this one is very inefficient. We have to perform a multiplication operation $n$ times! And who has time for that? Certainly not the students of the Masters Program in Computer Science.

Fortunately, there is a slightly-more-complicated-but-still-pretty-simple method called exponentiation-by-squaring that requires far fewer arithmetic operations. For example, imagine we wanted to find the value of $3^16$. Instead of multiplying 3 times itself 16 times, we could express this operation like this:

$((((3^2)^2)^2)^2)$

That’s just four multiplications instead of sixteen! Of course, in this case the exponent was conveniently a power of two. However, this trick also works for other exponents. For example, for $3^17$ we would just have to add an extra multiplication:

$((((3^2)^2)^2)^2) \cdot 3$

As it turns out, we can define exponentiation-by-squaring recursively (for all $x$ and $n$) like so:

$\exp (x, n) = \left\lbrace \begin{array}{l l} 1 & \text {if }n=0 \\ x & \text {if }n=1 \\ \exp (x \cdot x, \frac{n}{2}) & \text {if }n>1\text { and }n\text { is even} \\ \exp (x \cdot x, \frac{n-1}{2})\cdot x & \text {if }n>1\text { and }n\text { is odd} \end{array}\right.$

Your solution must use a RECURSIVE function, using the definition presented above.

On the exam, any other type of solution will receive zero points!

EVEN IF KATTIS JUDGES IT AS CORRECT!

## Input

The input contains two positive integers: $x$ and $n$, separated by a single space.

## Output

A single integer: $x^ n$, computed using the definition described above. You can assume $x^ n$ will fit in a 32-bit integer.

Sample Input 1 Sample Output 1
3 16

43046721

Sample Input 2 Sample Output 2
3 17

129140163

Sample Input 3 Sample Output 3
100 0

1

Sample Input 4 Sample Output 4
100 1

100

Hide