Done. xDDD
Thank you @aryanc403.I will check other editorials as well.
1 Like
Infinite loop? XD
Yes. xDDDD .
P.S. - Realised one more advantage of xD - bypass limit of 10 character. xD
1 Like
Yes, it guarantees factorization in LogN time. Glad you learned something from the editorial 
1 Like
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. 
1 Like
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.
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
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.