I tried the way as mentioned in the editorial, but am getting TLE on the 1st, 2nd and last Test Cases. I find my and ediorialist’s codes almost similar but couldn’t figure out why I am getting TLE. Is the O(MAX^2) complexity in every precalculation is causing TLE.
Secondly, I tried to sieve only up to the maximum element in the input array. It decreased the time of execution but all tasks gave WA.(Some still gave TLE)
Time Complexity:- O(XlogX+N) per test case, where X=1000000
On Computing time, it is similar to 2*10^7
and there can be 100 test cases at maximum, when i am assuming N=10^4
then total time will be over >10^9 still no TLE according to editorial… why? please SomeOne Explain where I am wrong
In the last section psuedo-code line no. 5 if freq[a[i]] > 0: should it not be changed to freq[i] > 0: here is the AC Code.
I have been trying to solve for subtask 1 but not getting an AC. Please someone help.
Can someone please explain, why the author is
when he is calculating good[i] array,
Need Help !!! Since I am a beginner I don’t understand How Counting is performed to clear subtask 2. I try to do the dry run in my rough copy but was not able to solve due to the huge size of the array. Can u plz tell me where I am lacking and which concept should I study to understand this. You can also share some link.
Can someone help me out ? I can’t find reason why it still TLE
Here is my code
CodeChef: Practical coding for everyone
Thank you!!
I tried implementing the solution in the editorial in Java. Its giving me TLE. Can someone please tell me why?
Solution Link: CodeChef: Practical coding for everyone
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
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.