Problem Link
Author: Ivan Fekete
Tester: Misha Chorniy
Editorialist: Bhuvnesh Jain
Difficulty
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.
