Let \(c(x)\) denote the number of occurrences of integer \(x\) in \(A\).

Among the triplets that satisfy the conditions, \(c(p)c(q)c(r)\) of them satisfies \(A_i = p, A_j = q\), and \(A_k = r\). Also, \(\frac{A_i}{A_j} = A_k \Leftrightarrow p = qr\).

Let \(M = \max_i A_i\). Obviously, if \(x > M\) then \(c(x) = 0\), and every element of \(A\) is an integer, so we can constrain the candidates of \((p, q, r)\) above to those such that:

• \(1 \leq p, q, r \leq M\),
• \(p = qr\),
• \(p, q\), and \(r\) are integers.

Once we could enumerate the triplets \((p, q, r)\), it is sufficient to take the sum of \(c(p)c(q)c(r)\) over all of such triplets.

Now, in fact we can prove that there aren’t so many triplets \((p, q, r)\) that satisfy the conditions described above. Since \(qr = p \leq M\), for a fixed \(q\) in the range of \(1 \leq q \leq M\), we can constrain the candidates of \(r\) to \(1, \dots, \left\lfloor \frac{M}{q} \right\rfloor\). Since \(p\) is determined by the value of \(q\) and \(r\), the number of triplets \((p, q, r)\) satisfying the conditions can be evaluated as:

\[\begin{aligned} \left\lfloor \frac{M}{1} \right\rfloor + \left\lfloor \frac{M}{2} \right\rfloor + \dots + \left\lfloor \frac{M}{M} \right\rfloor &\leq \frac{M}{1} + \frac{M}{2} + \dots + \frac{M}{M} \\ &\leq \left(\frac{M}{1}\right) + \left(\frac{M}{2} + \frac{M}{2}\right) + \left(\frac{M}{4} + \frac{M}{4} + \frac{M}{4} + \frac{M}{4}\right) + \dots + \left(\frac{M}{2^d} + \dots + \frac{M}{2^d}\right) \\ &= M(d + 1), \end{aligned}\]

where \(d\) is the maximum integer such that \(2^d \leq M\). Since \(d = O(\log M)\), it is shown that the number of triplets \((p, q, r)\) satisfying the conditions is \(O(M \log M)\).

Therefore, the problem can be solved in a total of \(O(M \log M)\) time by, for each \(q = 1, \dots, M\), iterating \(r\) in the range of \(1 \leq r \leq \left\lfloor \frac{M}{q} \right\rfloor\), and summing up the values of \(c(p)c(q)c(r) = c(qr)c(q)c(r)\).

Sample code (C++) :