Difference between (Line 135) ( lli mid=l+(r-l)/2 and lli mid=l+(r-l+1)/2 ) deserves a mention in CHEF VIJJU’S CORNER.
I missed the trick for storing lowest prime divisor for non primes. Good one!
i think the complexity should be k.N.logN, please correct if i am wrong.
2 Likes
another possible solution:
-
let g <- gcd of initial numbers
-
make a[i] = a[i] / g. new gcd = 1.
-
Now consider only primes until 100 to find the new solution. We will not be able to add any prime > 100 after the 2nd step. 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. let the answer for A[i]/g -> ans
final solution: ans * g.
This can be extended for A[i] <= 10^9 (by considering primes upto 1000).
let me know if I am wrong.
7 Likes
The tester solution is showing runtime error in my IDE.
I’m having difficulty in understanding the binary search part . Can you explain with some example.
What am I doing wrong?? I had the same logic but its giving me wrong answer.
Your solution is really too detailed，Thank you 
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
Done. xDDD