For simplicity, we first assume that the elements of \(A\) are pairwise distinct. Let \(\max A=M\).

We are to take sum over all pairs \((i,j)\) with \(i<j\). As the addends are symmetric for \(i\) and \(j\), one can rearrange the sequence \(A\) without changing the answer. We now assume that \(A\) is sorted in ascending order.

When \(A\) is sorted in ascending order, if \(i<j\) then \(A_i \leq A_j\), so \(\displaystyle \left\lfloor\frac{\max(A_i,A_j)}{\min(A_i,A_j)}\right\rfloor = \left\lfloor\frac{A_j}{A_i}\right\rfloor\).

For a fixed \(i\), consider each \(\displaystyle \left\lfloor\frac{A_j}{A_i}\right\rfloor\) instead of \(i\). That is, deform it as

\(\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^{N}\displaystyle \left\lfloor\frac{A_j}{A_i}\right\rfloor = \sum_{i=1}^{N-1}\sum_{n}n*f(A_i,n),\)

where \(f(d,n)\) is the number of \(j\) such that \(\displaystyle \left\lfloor\frac{A_j}{d}\right\rfloor=n\). (This replacement is equivalent to regarding for example “1+1+1+2+2+2+2+5+5” as “1×3 + 2×4 + 3×0 + 4×0 + 5×2”.

Let \(C_X\) be the number of \(i\) with \(A_i=X\). By precalculating the cumulative sum of \(C\), one can find \(f(d,n)\) in \(O(1)\) time. For a fixed \(i\), \(n\) ranges over \(n\leq \frac{M}{A_i}\), so the number of terms to take sum is \(\sum_{i=1}^{N-1}\frac{M}{A_i}\leq \sum_{d=1}^{N}\frac{M}{d}=O(M\log N)\) (sum of harmonic series).

Therefore, the problem has been solved in a total of \(O(M\log N)\) time.

Even if \(A_i\) has duplicating elements, one can handle them at once appropriately to find the answer in the same complexity.

writer’s solution (C)
writer’s solution (Python)