DIVPAIRS - Editorial

PROBLEM LINK:

Contest - Division 3
Contest - Division 2
Contest - Division 1

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Factorization

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

\begin{aligned} a\cdot c&\mid b\cdot d \implies\\ (g_1\cdot a')\cdot(g_2\cdot c')&\mid(g_1\cdot b')\cdot(g_2\cdot d')\implies\\ a'\cdot c'&\mid b'\cdot d' \end{aligned}

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

D_{i,1}\mid D_{j,2}\implies D_{i,1}=D_{j,2}'\\ D_{j,1}\mid D_{i,2}\implies D_{j,1}=D_{i,2}'

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

\sum_{f\in F} dp_i[f][D_{i,1}]

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

O(N\log N+N\sqrt X)

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

You can do it in \mathcal{O}(N log N + N (\max A_i)^{\frac{1}{3}})code

3 Likes

how to calculate such precise time complexity

Analyze all segments of the solution separately

Hi, can you please explain your approach