I was trying to hack some solution for problem D of yesterday's contest. Now, as far as I know, the solution which are running loop on all the primes should be failed in hacks, as the time complexity is around O(# of primes)*O(n). This is around $$$7.8*10^8$$$. And all these solutions are running in 2 seconds if they have used some thing like fast input output.
I think that the bounds in the problems should have been tighter for this to not happen... What do you guys think about this?
The intended solution should be $$$O(n \sqrt A)$$$ which is clearly larger than what you suggest. $$$O(n \log A)$$$ is possible with preprocessing using a sieve but of course then it would be harder than regular Div3D.
Yeah! I totally agree with you with the $$$O(n \sqrt{A})$$$ solution.
But I was saying about other solutions... The ones which calculate the primes till $$$10^6$$$ and then for every $$$a[i]$$$, run loop on every prime till $$$10^6$$$ and divide $$$a[i]$$$ with it...
Well, that kinda sucks. But a larger bound on $$$A$$$ should make the $$$O(n\sqrt{A})$$$ TLE also. Anyways, the solution you described is $$$O(n \frac{A}{\log A})$$$, so we can't just blame the bounds.