I was trying to solve this coding question.
You are given an integer $N$ and a value $k$. You need to find a minimum number $X$ which when multiplied to $N$ results in the value of $N^{1/k}$ as an integer.
For example let $N = 6$ and $k = 2$ and , then the answer will be $6$ because $ 6 * 6 = 36 $ and if we calculate $36 ^ {1/2}$ it is equal to $6$ which is an integer.
Constraints
$1 < N < 10 ^ {12}$
$1 < k < 10 ^ {12}$
I realized that we needed to find the the minimum integer $X$ which when multiplied to $N$ gives the closest kth root.
for example with $N = 12$ and $k = 2$
Kth Power
1
4
9
16
25
36
Starting from $N ^ {1/ k}$ I iterated over over each of kthPower $p^k$
Thus the equation become finding the first $X$ where $X$ is a whole number from the below equation
$\frac{p^k - N}N = X$ where $p$ starts from $ceil(N^{1/k})$
This approach loops through each possible power and hence isn't the most efficent solution. Can you help me solve this equation so that we can avoid looping and have better run time complexity.
Note that if $m$ is a perfect $k^{th}$ power, then every prime factor must appear some multiple of $k$ times. So what you should do is factor $N$, and find the smallest number you can multiply by so that all of its prime factors appear some multiple of $k$ times.