Problem LinkAuthor: Ivan Fekete Tester: Misha Chorniy Editorialist: Bhuvnesh Jain DifficultyEASY PrerequisitesSieving Techniques ProblemLet $S(x)$ denote the sum of distinct prime divisors of $x$. Find the number of pairs $(i, j)$ in array $A$ such that if $A[i]$ divides $A[j]$ then $S(A[i])$ also divides $S(A[j])$. ExplanationLet us first calculate the function $S$ for all integers efficiently. This is a simple modification of the prime sieve where we add the contribution each prime divisor to the numbers as well.
The time complexity of the above approach will be $O(\sum_{p = prime} X/p) = O(X \log{\log{X}})$, where $X = 1000000$. Let us also calculate the good pairs of numbers. Below is a pseudocode for it:
The time complexity of the above approach is $O(\sum_{i=2}^{i=N} X/i) = O(X \log{X})$, where $X = 1000000$. If you have any doubts regarding the above 2 precomputations, I suggest you to learn and read Sieve of Eratosthenes and try to understand how the code is modified here. Now, coming back to the problem. We need to find the number of pair of $(i, j)$ in array $A$ such that if $A[i]$ divides $A[j]$ then $S(A[i])$ also divides $S(A[j])$. For this, if we do it naively for every pair using the help of above precomputation to check if $A[i]$ and $A[j]$ is good, then it will inefficient and only pass subtask 1. The important thing to note that even if we iterate over all "good" arrays, the total size of all arrays is bounded by $O(X \log{X})$, considering all the numbers are appended. Actually, this bound is lower, but it doesn't matter. So, let say if we have the frequency of all elements in the array $A$. When iterating over the "good" array, if $2$ numbers have frequency $x$ and $y$ then they contribute $(x * y)$ to the answer. The only caveat is that pair $(i, i)$ i.e. same pair of indices is also counted in it. So, we need to subtract $N$ from the final answer as well. Thus, the below psuedocode can easily solve our complete problem:
Once, you are clear with the above idea, you can see the editorialist implementation below for help. Feel free to share your approach, if it was somewhat different. Some ThoughtsThere exist a linear sieve for prime numbers as well. Can you modify the first algorithm for precomputation of $S$ to work in linear time? If yes, how? If no, what is your counter argument? Time Complexity$O(X \log{X} + N)$ per test case. Space Complexity$O(X \log{X})$ AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. Tester's solution can be found here. Editorialist's solution can be found here.
This question is marked "community wiki".
asked 28 Jul '18, 17:31

This should be freq[a[i]] = 1. Correct it answered 29 Jul '18, 02:02

@likecs could you please clear the linear sieve and an additional O(n) array approach? answered 29 Jul '18, 12:33
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"
(29 Jul '18, 13:05)

We cannot use linear sieve for precomputation of $S$. Because linear sieve makes sure that each n is visited by it's lower prime no. And is only visited once. But For computation of we have to visit each distinct prime factor of no. And there are atmost 6 distinct factors for nos upto 1e6. answered 29 Jul '18, 01:46
@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?
(29 Jul '18, 02:05)

I am sure I did the same, but still wasn't able to pass subtask 6. Could someone provide some pointers: https://www.codechef.com/viewsolution/19375192 Thanks. answered 29 Jul '18, 02:01
2
Overflow error. Your soln https://www.codechef.com/viewsolution/19384172 . Changes made  E.g.  Test case
(29 Jul '18, 02:34)
Congrats man you again proved that we should not use \% until and unless it is absolutely necessary.
Your soln with removed With this correct my soln (which I used in contest) similar to your now passes.
(29 Jul '18, 02:40)
@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.
(29 Jul '18, 02:43)
Its always stuff like this! Thanks @aryanc403, I hope this will make me remember about overflow during int arithmatic.
(29 Jul '18, 19:14)

Thanks @fr4nkesti3n , Approach Sieve to find $S[i]$ Editorials soln can be optimised further by using set/map for outer loop. By in that case insertion complexity will be $O(logn)$ And overall complexity will be again $O(NlogN)$ . answered 29 Jul '18, 04:54

Hello everyone,I m getting TLE in last test cases and i m not able to figure out the reason..please help me out. answered 29 Jul '18, 15:14

Can someone point out what was wrong with my code (I was targeting for subtask 1) https://www.codechef.com/viewsolution/19376505 answered 30 Jul '18, 11:11
1
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.
(30 Jul '18, 23:22)

After trying to understand it for 10hrs and after doing nearly 15 submissions, I am still struggling to get AC. please check my PA Solution here and tell me what I am missing. answered 30 Jul '18, 21:19
Either use
(30 Jul '18, 21:29)
okay got it...looks like someone already asked this question before thanks :))
(31 Jul '18, 18:52)

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) answered 31 Jul '18, 00:36
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.
(31 Jul '18, 01:00)
Okay, got it, Thanks :)
(31 Jul '18, 14:18)

I have been trying to solve for subtask 1 but not getting an AC. Please someone help. answered 01 Aug '18, 05:39

@likecs It will have 10^9 (approx) computations.How will it be completed in 1 sec? answered 02 Aug '18, 01:02

Can someone please explain, why the author is ensuring that "i" divides "j" ?when he is calculating good[i] array, does he mean if "i" doesn't divide "j" => "s[i]" doesn't divide "s[j]" ?answered 02 Aug '18, 10:18

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. answered 02 Aug '18, 19:19

Can someone help me out ? I can't find reason why it still TLE Here is my code https://www.codechef.com/viewsolution/19452525 Thank you!! answered 04 Aug '18, 09:46

I tried implementing the solution in the editorial in Java. Its giving me TLE. Can someone please tell me why? Solution Link: https://www.codechef.com/viewsolution/19435752 answered 13 Aug '18, 10:10

In java you can implement editorial's method like this: (I was getting TLE if I preprocessed using Lists of Java) answered 16 Aug '18, 00:42

Author's solution link is wrong. It should be for the tester. Correct one is : https://ideone.com/b1dJXm
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 :(