Can you please explain with the help of an example?
The proof to my solution:
Let g be the gcd of A[i]s.
Now the gcd of A[i]/g to will be 1. (Pretty straight forward to see. Consider gcd be x. If gcd > 1, it contradicts that gcd of A[i] is g as every A[i] will then be divisible by g*x)
Now consider any number d> 100. In the best case, d can divide (n-1) numbers and maximum power of d on any of the nimber is 2. So, consider that d^2 divides (n-1) numbers. Now we have 2 cases:
-
Divide a number by d^2 and multiply the last number by d. The will make the last number divisible by d but the number which was divided by d^2 no longer divisible by d. Which brings us to the same position except now we have (n-2) numbers divisible by d^2 and 1 number divisible by only d and last number still not divisible by d.
-
Divide the number by d^2 and multiply a number which was already divisible by d^2 by d. In this case, tgere are (n-1) numbers divisble by d^2, 1 by d^3 (lets say this a) and 2 numbers non divisble by d. If you try to divide a by d^2 then a will be divisible by d and multiply a number no divisble by d. It will brng us to the same case as above. (You can prove this by induction that this will also not work)
You can also see that the numbers cant be made divisible by d by using the tester can function for md=1. You need 1 more divisor, how ever you can get int((2-1)/2) * (n-1) divisors = 0.
I rest my case.
2 Likes
for (int k : id[x])
if (k >= h)//Find excess power
now += ((k - h) >> 1); // sum, that we can use
for (int k : id[x])
if (k < h)//Find deficit power.
now -= (h - k); // sum, that we need
Consider this part of the code, it has O(n) complexity in itself.
So the overall complexity should be O(k.n.lg(H)) per test case.
Correct me if I’m wrong anywhere.
1 Like
If anyone can tell me why code is giving me a run error it’ll be great 
https://www.codechef.com/viewsolution/19341290
Very nice,detailed and easy to get editorial.Really loved it.
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?
https://www.codechef.com/viewsolution/20550090
Can some one help me understand, why is my solution giving wrong answer.
problem links are pointing to different problem bro. Nice work btw
Thanks for telling that. The time in hand to prepare editorials was lesser than a drop of sand xD
Thank you @aryanc403.I will check other editorials as well.
Infinite loop? XD
Yes, it guarantees factorization in LogN time. Glad you learned something from the editorial 
Why does the condition in the binary search use (r - l > 1) instead of (r > l)?
There are many variants of binary search. Nothing special in that condition.
Its that, if r-l=1, then mid will always be equal to l. Might result in infinite loop. So setter kept r= Max Possible Value+1 (i.e, our answer is between [l,r) instead of [l,r]).
Nicely Explained! Keep it up bro
https://www.codechef.com/viewsolution/19318590
using setter solution but only considering primes until 100.
it does not matter. storing any prime would suffice as smallest prime = 2. So in each iteration number n is getting reduced to atmost n/2, therby guaranteeing factorization in log(n).
Good job.
This can be extended for A[i] <= 10^9.
I doubt that. The reason is that your assumption - let d be a prime > 100 such that d^2 is divisible by A[i], then if we divide this A[i] by d^2 then A[i] will no longer be divisible by d. will not hold.
Currently, A_i \le {10}^{6}, so say if p>100. If we say that A_i is divisible by p even after dividing by {p}^{2}, then A_i \ge {p}^{3} \implies A_i > {100}^{3} (as p>100) \implies A_i >{10}^{6}. Since A_i \le {10}^{6}, this means p<100
This will not hold for {10}^{9}
Yes, the trick is to store a prime divisor. Else you’d have to factorize in \sqrt{N} which can be a problem at times.