Not very straightforward dear. If you assume that the for(int k:id[x]) runs for all N numbers everytime, what is the maximum number of times it can run?
A number can be product of <20 distinct prime numbers if A_i \ {10}^{6}. So the complexity becomes O(20*N*LogN) \equiv O(NLogN) as shown in editorial.
If binary search part isnt clear, then you dont fulfil the pre-requisites to solve the question. Please refer to links in pre-requisites.
If anyone can tell me why code is giving me a run error it’ll be great 
https://www.codechef.com/viewsolution/19341290
@vijju123 Bro, see these lines–>
for (int k : id[x])
if (k >= h)
now += ((k - h) >> 1); // sum, that we can use
for (int k : id[x])
if (k < h)
now -= (h - k); // sum, that we need
in idx[x] where x is prime, holds exponent of x in every A[i](excluding if exponent is 0)
so i guess overall complexity will be O(NLogN+k.(summation of number of element id[x] for each prime)*logH)…
if i am right, can u prove that this solution will not give TLE ?
Very nice,detailed and easy to get editorial.Really loved it.
The vector array power needs to be cleared for every new testcase
Thank you
please someONe reply?
I had answered this already in an ans on next page.
I say, lets try to get an upper bound on number of iterations. It cannot be O(N*K) as that’d mean every array element A_i is divisible by each of k primes - not possible based on my previous arguments.
At max, how many iterations can it go then? Each element A_i is divisible by <log_2N primes. So worst case calculated by me was select logN smallest primes such that their product is <{10}^{6}. Let it be X. Make an array with N-1 elements X and one element 1. That gave O(NLogN) complexity.
Convert recursive to iterative one.
@vijju123 got Ac, my finding smallest factor for each number using seive was slow regarding max A[i]=10^6…
*O(A[i].log[Ai]) ~~ 2 * 10^8 ==tle
so optimised my code little bit, got ac
now my code is fastest among all java submission for this problem… thanks for replying
Can it be done in this manner:
Calculate total number of times a prime number appears in the factorization of every array elements like in example 3,15,15,27,1024 total number of 3’s are six and 2’s are ten.
Now simply multiply all the prime numbers with count greater than or equal to number of elements+1.
Please tell me if I am wrong?
I found this method also; shake out the initial gcd and then only primes below the cuberoot of the limit can support the 2-for-1 deal.
https://www.codechef.com/viewsolution/20550090
Can some one help me understand, why is my solution giving wrong answer.