# PRMDIV - Editorial

Practice

Contest

Author: Ivan Fekete

Tester: Misha Chorniy

Editorialist: Bhuvnesh Jain

EASY

# Prerequisites

Sieving Techniques

# Problem

Let 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]).

# Explanation

Let 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.


S[1] = 0
for i in [2, 1000000]:
if S[i] == 0:
# number is prime
j = i
while j <= 1000000:
S[j] += i
j += i



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 pseudo-code for it:


# good[i] stores the "j" such that
# "i" and "S[i]" divide "j" and "S[j]" respectively.
for i in [2, 1000000]:
j = i
while j <= 1000000:
# Ensured that "i" divides "j". See the loop conditions.
if S[j] % S[i]:
good[i].append(j)
j += i



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 pre-computation 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 psuedo-code can easily solve our complete problem:


for i in [1, n]:
freq[a[i]] += 1
ans = 0
for i in [2, 1000000]:
if freq[i] > 0:
# Element is present
for j in good[i]:
ans += freq[i] * freq[j]
# Account for i == j
ans -= n
print ans
# Clear freq array for next test case.
for i in [1, n]:
freq[a[i]] -= 1



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 Thoughts

There exist a linear sieve for prime numbers as well. Can you modify the first algorithm for pre-computation 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.

2 Likes

Authorâ€™s solution link is wrong. It should be for the tester. Correct one is : https://ideone.com/b1dJXm

1 Like

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

We cannot use linear sieve for pre-computation 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.

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.

1 Like

# Clear freq array for next test case.

for i in [1, n]:
freq[a[i]] += 1


This should be freq[a[i]] -= 1. Correct it

1 Like

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?

Does it EASY?

Overflow error. Your soln https://www.codechef.com/viewsolution/19384172 .

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.

Thanks @fr4nkesti3n ,

My AC approach here -
I was just trying luck along with double sieve. Hence I used a variable named lucky. xD. In case I get AC this is reason behind it.

# Approach -

Sieve to find S[i]

Maintain Counter Array.

Used Map. Although Set is more appropriate then Map

Brute force for 1<=a[i]<=lucky. With lucky<=100 Atmost 100 iterations.

For a[i]>lucky. One loop for 1<=i<=lucky and rest sieve. Atmost 200 iterations.

But still in TL .

Unfortunately it failed on last test case. And I made 15 submissions with different values of lucky with hope of getting AC.

Finally I got AC after seeing @fr4nkesti3n soln.

And bingo it resulted in A.C. Soln.

Never use % until and unless it is absolutely necessary.


I repeat Never use % until and unless it is absolutely necessary.

It can take you from 100 pts to 20 pts And you will never realise reason behind it.

He added condition if(cnt[j]) then only compute s[j]\%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) .

1 Like

@likecs in the pseudocode to calculate the final answer

for i in [2, 1000000]:
if freq[a[i]] > 0:
# Element is present


Shouldâ€™nt it be freq[i] instead of freq[a[i]] ?

@likecs could you please clear the linear sieve and an additional O(n) array approach?

1 Like

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â€ť

Hello everyone,I m getting TLE in last test cases and i m not able to figure out the reasonâ€¦please help me out.
Here is the link to my solution:- https://ideone.com/XUhDs1