Simple-Math, Prime-Factorization, Fast-Exponentiation
Given an array of numbers, make all elements equal by the following operation.
Divide a number by x if it is divisible Multiply another number by x.
You may insert another number to do so.
Let’s call p, the product of all numbers. The answer is “justdoit” if it’s n-th root is a natural number. Else, find the smallest number such that the (n+1)th root of p is a natural number.
We have some key observations here -
1. The operation of dividing a number by X, and multiplying other number by X, can be thought of multiple operations in which we are dividing only by primes, and multiplying only by primes. 2. These primes will be nothing but the all the primes in the prime factorization of X (If a prime p divides X k times, the p will be repeated k times).
So, the problem can be thought of solving individually for each prime.
Let us try to understand what happens for a prime p.
Let us create a list of sum of exponents of p in each A[i].
We want all the elements in this array to be equal.
In a single operation, we can decrease some element and increase the other.
It will be possible to make them equal if each of the element is divisible by n.
Otherwise, you will have to add another exponent such that each element S becomes divisible by n+1 (+1 due to the extra element we are adding).
Suppose the element we are adding has exponent L.
Then, (S+L)(n+1) should be 0. Or, L = 0 if S(n+1) == 0 else L = (n + 1) - s % (n + 1)
So, now we know the exponent for each prime factor of the next number.
The next number will be equal to the product of all (its prime factors)^(its exponent).
Remember to take modulo at each step.
a^b % MOD can be calculated quickly using fast-exponentiation.