UVa 113 - Power of Cryptography

This problem made me suffer a little bit! Given two positive integer $n$ and $p$, this problem asks to find a positive integer $k$ such that $k^n = p$, or in other words, $k$ is the positive $n$-th root of $p$.

My initial attempt was to use binary search. We guess on the value of $k$ and check if our guess is correct. As $1 \leq k \leq 10^9$ and $n$ is fixed, as $k$ is increased so does the value of $k^n$ and so the the monotonicity property is fulfilled (Increasing or decreasing $k$ will increase or decrease $k^n$ and so can incrementally close in on the range where the answer lies). The only caveat is checking if our current guess of $k$ value is valid or not.

Because the value of $p$ can be massive ($p < 10^{101}$), we have to use either double or string data type to store $p$. string operations are expensive, unless the multiplication is done efficiently. C++ has no built in BigInteger class like Java, and so a naive $\mathcal{O}(n^2)$ multiplication will likely exceed the time limit. Java implements more efficient multiplication algorithms like Karatsuba $\left(\mathcal{O}(n^{1.585})\right)$ or Toom-Cook $\left(\mathcal{O}(n^{1.465})\right)$ from Java 1.8 onwards. The following implementation uses BigInteger library of Java:

We can write our own BigInteger class/library in C++, but it wouldn’t be very efficient and to come up with something efficient will require significant amount of time and effort. So, let’s throw string out of the picture and focus on double. How is double represented in C++? See the following picture:

double is in the format $\pm 1.\textrm{mantissa} \times 2^{\textrm{exponent}}$.