# Problem D

Don'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:

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 |