UVA 10622 - Perfect Pth Powers

http://uva.onlinejudge.org/external/106/10622.html

We say that x is a perfect square if, for some integer \(b\), \(x = b^{2}\). The perfect pth power for a given number \(x\) is defined as  \(x = b^{p}\). You need to determine the largest \(p\) such that \(x\) is a perfect pth power. 

This problem main idea is based on the understanding of the prime factors exponents divisibility. Let's begin with a proof that is going to help us  understand this concepts. Theorem: all the powers in the prime factorization of an integer \(n\) are even if and only if \(n\) is a perfect square, proof:

$$\\\\ n = p_{1}^{k_{1}}p_{2}^{k_{2}} \cdots p_{t}^{k_{t}} \\\\ m = n^{2} \\\\ m = (p_{1}^{k_{1}}p_{1}^{k_{1}})(p_{2}^{k_{2}}p_{2}^{k_{2}}) \cdots (p_{t}^{k_{t}}p_{t}^{k_{t}}) \\\\ m = p_{1}^{k_{1} + k_{1}}p_{2}^{k_{2}+k_{2}} \cdots p_{t}^{k_{t}+k_{t}} \\\\ m = p_{1}^{2k_{1}}p_{2}^{2k_{2}} \cdots p_{t}^{2k_{t}}$$

Because all the exponents of m are even we can conclude that is perfect square.We can easily extend the previous proof to powers of 3, 4, ..., all the way to \(n\). This means that if all the exponents in the prime factorization of a certain number \(x\) are divisible by a certain number \(p\) we can express this number as a pth power. To implement this idea we factorize the number in his standard prime factorization, and, for each factor frequency check the divisibility against certain number pth. If all the number pass the test we got our pth power, is guarantee to always get an answer because of the 1th powers.

The only thing left to consider is the cases when the number \(x\) is less than zero. Let's consider the following example \(4096 = 2^{12}\) but, -4096 is not \((-2)^{12}\). In order to get a negative number as a result of repeated multiplication of the same number, we need to multiply that number odd times. Which means that in the case of negative number we stay with the biggest odd pth exponent as it shows in the following expression:

$$-4096 \Rightarrow (-2)^{12} \Rightarrow (-2)^{3\cdot 4} \Rightarrow (-16)^{3}$$