D - Index Trio

$\frac{A_i}{A_j} =A_k$ を変形すると、 $A_i = A_jA_k$ となります。
$A_i$ を固定すると、 $A_j,A_k$ は $A_i$ の約数の組に限定されます。
よって、 $A_1,...,A_N$ について、 $1\leq d \leq \lfloor \sqrt{A_i} \rfloor$ である約数 $d$ についてのみ調べれば良く、各 $A_i$ について、 $O(\sqrt{A_i})$ で全探索できます。

計算量は、 $A$ の最大値を $A_{max}$ として、 $O(N\sqrt{A_{max}})$ となり、間に合うか微妙なところですが大丈夫でした。

$A_i=d\times \frac{A_i}{d}$ となる組が何通りあるかですが、
$cnt_{x}$ を $A$ に出現する $x$ の個数とすると、

$cnt_{d} \times cnt_{ \frac{A_i}{d}}$

となります。
これは、 $A_j = d$ となる全ての $A_j$ に対して、 $A_k = \frac{A_i}{d}$ となる $A_k$ と組を作ることができるためです。

$1\leq d \leq \lfloor \sqrt{A_i} \rfloor$ である $d$ について組を計算するわけですが、 $d\neq \frac{A_i}{d}$ である場合、組の順序を入れ替えると別の組になるので、2倍します。
逆に、 $d = \frac{A_i}{d}$ の場合は入れ替えてできる組は同じなので、2倍しません。

提出コード Submission #31196140 - Monoxer Programming Contest 2022（AtCoder Beginner Contest 249）

なお、計算量を落とすことが可能です。
$1,2,...,A_{max}$ の全てについて、エラトステネスの篩と同じ方法で、試し割り不要で約数が記録された二次元配列を得ることが可能です。
計算量は $O(A_{max}logA_{max})$ となり、二次元配列のサイズも同様に $A_{max}logA_{max}$ となると考えられます。