# Powerful Number

Criterion 2022 Round 16

The number $x^y$ is powerful. Let the prime factorization of $x$ be $p_1^{e_1} \times p_2^{e_2} \times p_3^{e_3}\times … \times p_k^{e_k}$, then the prime factorization of $x^y$ will be $p_1^{y.e_1}\times p_2^{y.e_2} \times p_3^{y.e_3} \times ... \times p_k^{y.e_k}$. So the power of each prime of $x^y$ is a multiple of $y$.

Let the prime factorization of $n$ be $p_1^{e_1} \times p_2^{e_2} \times p_3^{e_3} \times … \times p_k^{e_k}$ and the maximum among $e_1, e_2, e_3, …, e_k$ be $e$. If $y > e$, then $x^y$ must be greater than or equal to $n^2$. As we know, $n^2$ is a powerful number, $n$ is a probable value of $p$ and we don’t need to care about the values greater than $n^2$. There may exist some smaller value than $n^2$ which is powerful. To find them, we can iterate from $2$ to $e$ and for each $2 \leq i \leq e$, we want to find the minimum value $p_i$ required to make $n$ in the form $x^i$. The number $n\times p_i$ is in the form $x^i$ iff the power of each prime divisor of $n$ is a multiple of $i$. So, for each $i$, we can multiply each prime the minimum number of times such that the power of that prime is a multiple of $i$. The answer is the minimum among all such $p_i$.

The only exception is when $n$ is $1$. In this case, the answer is $4$. Time complexity is $O(k)$ for each test case where $k$ is the total number of primes less than $\sqrt{n}$.

### Statistics

42% Solution Ratio
NirjhorEarliest, 3M ago
arnab_1810043Fastest, 0.0s
anisur_rahmanLightest, 131 kB
jewel.samaShortest, 987B