簡単のため、\(A\) が相異なる場合を考えます。\(\max A=M\) とします。

和を取るのは \(i<j\) を満たす全てのペア \((i,j)\) に対してであり、和を取る対象が \(i,j\) に関して対称であるため、数列 \(A\) を並び替えても答えは変わりません。よって \(A\) は昇順にソートされているとしてよいです。

\(A\) が昇順にソートされているとき、\(i<j\) ならば \(A_i \leq A_j\) であることから、\(\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\) となります。

\(i\) を固定したとき、\(j\) を動かすのではなく、\(\displaystyle \left\lfloor\frac{A_j}{A_i}\right\rfloor\) の値を動かすことを考えます。すなわち、

\(\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)\)

と変形します。ここで、\(f(d,n)\) は \(\displaystyle \left\lfloor\frac{A_j}{d}\right\rfloor=n\) を満たす \(j\) の個数とします。（この変形は、例えば「1+1+1+2+2+2+2+5+5」を「1×3 + 2×4 + 3×0 + 4×0 + 5×2」と計算するものです）

\(A_i=X\) となる \(i\) の個数を \(C_X\) として、あらかじめ \(C\) の累積和を計算しておくことで \(f(d,n)\) は \(O(1)\) で求めることができます。また、\(i\) を固定したとき \(n\) の動く範囲は \(n\leq \frac{M}{A_i}\) であることから、和を取る項の個数は \(\sum_{i=1}^{N-1}\frac{M}{A_i}\leq \sum_{d=1}^{N}\frac{M}{d}=O(M\log N)\) です。（調和級数の和）

よって以上より \(O(M\log N)\) でこの問題が解けました。

\(A_i\) が同じ要素を持つ場合も、それらを適切にまとめて計算することで同じ計算量で求めることができます。

writer解(C)
writer解(Python)