PROBLEM LINK:
Contest - Division 3
Contest - Division 2
Contest - Division 1
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
PROBLEM:
Given array A, compute the number of unordered pairs (i,j) such that i\cdot j divides A_i\cdot A_j.
EXPLANATION:
Create an array of pairs C whose elements are (i, A_i) for all 1\le i\le N. Let C_{x,1} and C_{x,2} represent the first and second elements of the pair C_x, respectively.
Call a pair of pairs (C_i,C_j) special if C_{i,1}\cdot C_{j,1} divides C_{i,2}\cdot C_{j,2}. Then. we want to find the total number of unordered pairs (C_i,C_j) that are special.
Start by dividing C_{i,1} and C_{i,2} by \gcd(C_{i,1}, C_{i,2}), for all i. Let the resulting array of pairs be D.
Claim: (D_i,D_j) is special iff (C_i,C_j) is special.
Proof
For clarity, lets define C_i = (a,b) and C_j = (c,d). Also, let g_1=\gcd(a,b) and g_2=\gcd(c,d). Finally, define D_i=(a',b') and D_j=(c',d'), where a=g_1\cdot a', b=g_1\cdot b', c=g_2\cdot c' and d=g_2\cdot d'.
Then, (C_i,C_j) is special implies
implying pair (D_i,D_j) is also special.
So, the problem is equivalently reduced to finding the number of special unordered pairs of D.
Claim: (D_i,D_j) is special iff D_{i,1}\mid D_{j,2} and D_{j,1}\mid D_{i,2}.
(The proof is trivial and left to the reader as an exercise; Use the fact that D_{i,1} and D_{i,2} share no common factors.)
Therefore, if (D_i,D_j) is special, then
where D_{i,2}' and D_{j,2}' are factors of D_{i,2} and D_{j,2} respectively.
Let dp_i[x][y] represent the number of j\space(j<i) such that x=D_{j,1} and y\mid D_{j,2}.
It is not too hard to see (using the above deductions) that the number of j\space(j<i) such that (D_j,D_i) is special is equal to
where F is the set of all factors of D_{i,2}.
Summing this value over all i gives us the required answer!
Implementation
Maintain a 2d hash table (nested unordered_map<>
in C++) to hold the values of dp_i. Let’s call it DP. Currently, hash table DP is empty.
Iterate from 1 to N. Let i be the current index we are processing.
Calculate all factors of D_{i,2} quickly, using sqrt decomposition. Then, for each factor f, add DP[f][D_{i,1}] to the answer. Finally, update the hash table by adding 1 to DP[D_{i,1}][f] for all factors f.
TIME COMPLEXITY:
Calculating array of pairs D takes O(N\log\max(i,A_i))\approx O(N\log N) (the log factor is present because we have to compute the gcd).
Updating the DP table after processing each D_i can be done in O(\sqrt{D_{i,2}})\approx O(\sqrt X) time, where X=\max A_i.
Assuming constant time lookups and updates to table DP, the total time complexity is equal to
per test case.
SOLUTIONS:
Editorialist’s solution can be found here.
Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)
- 1
- 2
- 3
- 4
- 5
0 voters