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.
The time complexity is derived from tester’s solution. He first factorises all array elements in O(NLogN), and then for every prime he applied binary search O(kLogH) where H is the highest power of that prime.
Thats because of their assert statements. Codechef IDE adds extra character at end of file. One way around is, to remove the assert(getchar() == -1); at the end and give 1 extra line after input.
Their assertions are done to make sure there are no trailing spaces in input etc. which might cause NZEC error for some java and/or python users.
OR
replace their assert statements with simple cin/cout or scanf/printf 
1 Like
Ohh!!..Okayy, actually there was a mistake in my binary search…I was trying to find that…A great editorial though @vijju123…
1 Like
Thank you
for A[i]<=10^9 we will need to consider primes till 1000.
in general for any n, we need to consider primes till n^1/3.
sorry for not explicitly mentioning that.
2 Likes
inside the while loop of binary search, there is also a for loop which can go upto n, so i think it should be O(k.n.logH)
1 Like
Yesss. Exactly!
Infact, if you consider primes upto {10}^{6}, I feel we can solve it for A_i<{10}^{18} as well. Very decent effort from your side
I’m having difficulty in understanding the binary search part . Can you explain with some example.
Do you have any prior experience on “Binary Search on Answer”? If no, then please refer to links of pre-requisites or practice a few problems from hackerearthon that specific topic.
What am I doing wrong?? I had the same logic but its giving me wrong answer.
Your solution is really too detailed，Thank you
an excellent observation
Can you please pinpoint the location? Cannot get it.
Thank you dear
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
k.n is of the order n.log(n) as any number can have at-most log(n) factors.
So, the actual complexity is n.log(n).log(h).