D - Index Trio Editorial by spheniscine


Let \(m := \max_i A_i\). Also let \(C_x\) be the number of occurrences of \(x\) in \(A\).

Then the answer can be found by:

\[\sum_{x = 1}^m \sum_{y = 1}^{\lfloor m / x \rfloor} C_x \cdot C_y \cdot C_{x \cdot y}\]

where values \(x, y, x \cdot y\) represent \(A_j, A_k, A_i\) respectively.

Time complexity: \(O(N + m(1 +\frac 1 2 + \frac 1 3 + ... + \frac 1 m)) = O(N + m \log m)\), via the partial sum of the harmonic series.

posted:
last update: