In java you can implement editorial’s method like this:
https://www.codechef.com/viewsolution/19737889
(I was getting TLE if I pre-processed using Lists of Java)
Author’s solution link is wrong. It should be for the tester. Correct one is : b1dJXm - Online C++0x Compiler & Debugging Tool - Ideone.com
I was so close to a full AC in this one. I didn’t realize we could precompute the good pairs and store them to speed up each test case. TLE on the absolute last test case 
Correct. Check again.
@aryanc403, think you. Hint: The answer is yes and instead of using only the linear sieve, we can use an additional O(N) loop again. Do you get some hint or more is required?
Overflow error. Your soln CodeChef: Practical coding for everyone .
Changes made - pairs += a[i] * ((long long)a[k]); and pairs += a[i] * (a[i] - 1L);
E.g. - Test case T=1; n=1000000; a[i]=3; ans ~ 1e12 > INT_MAX
2 Likes
Congrats man you again proved that we should not use % until and unless it is absolutely necessary.
Your soln with removed if(a[k]) results in TLE.
https://www.codechef.com/viewsolution/19384237
With this correct my soln (which I used in contest) similar to your now passes.
@vijju123 I think there is some problem with counting upvotes on this answer. I upvoted but it is showing 0 upvotes. And his profile does not show any downvote. And If I un upvote this answer then it is showing -1 votes.
Correct. Please check again.
Hint 2: Linear sieve stores smallest prime factor for every number. In the second loop, we will use a DP solution. Say we have computed answer till some point, how can handle transition for “x”, say using the answer from “x / lp[x]” where lp[x] denotes lowest prime factor of “x”
Reason is already answered. Check this page again.
Its always stuff like this! Thanks @aryanc403, I hope this will make me remember about overflow during int arithmatic.
ans += freq[i]*(freq[i] - 1) ;
ans += freq[i]*freq[good[i][j]] ;
Either use ans += 1LL*freq[i]*(freq[i] - 1) ; etc or use long long.
for(int i=2;i<=sqrt(MAX);i++) => Mistake is here, this is enough to compute if a number is prime is or not but not enough to calculate S[x]. Think about counter examples.
1 Like
https://www.codechef.com/submit/complete/19404615
Your AC code. A judicious and appropriate use of data structures is a must. Your map gave a heavy, extra logN factor. Also, use arrays wherever possible.
Okay, got it, Thanks 
okay got it…looks like someone already asked this question before
thanks :))
Its typo. Corrected it.
waiting for reply… plz someOne help
Because at any instance, only {10}^{4} of the {10}^{6} elements will be present in an array. This reduces time complexity. Further, if operations are basic,such as addition etc. then its easy to get {10}^{8}-{10}^{9} operations done in a second.