P10390 [Lanqiao Cup 2024 NOI Qualifier A] Divisor Counting

Xiaolan casually wrote down an array $\{a_1, a_2,\cdots, a_n\}$ containing $n$ positive integers. He found that he can easily count how many ordered pairs $(i, j)$ satisfy that $a_j$ is a divisor of $a_i$. Therefore, he defines an integer pair $(x_1, y_1)$ to be a “divisor” of another integer pair $(x_2, y_2)$ if and only if $x_1$ and $y_1$ are divisors of $x_2$ and $y_2$, respectively. He wants to know how many ordered quadruples $(i, j, k, l)$ satisfy that $(a_i, a_j)$ is a divisor of $(a_k, a_l)$, where $i, j, k, l$ are all distinct.

The first line contains a positive integer $n$. The second line contains $n$ positive integers $a_1, a_2,\cdots, a_n$, separated by a single space.

Output one line containing an integer representing the answer.

Quadruple $(1, 4, 2, 3)$: $(3, 2)$ is a divisor of $(6, 2)$. Quadruple $(1, 3, 2, 4)$: $(3, 2)$ is a divisor of $(6, 2)$. Quadruple $(4, 1, 3, 2)$: $(2, 3)$ is a divisor of $(2, 6)$. Quadruple $(3, 1, 4, 2)$: $(2, 3)$ is a divisor of $(2, 6)$. Constraints: For $20\%$ of the testdata, $n \le 50$. For $40\%$ of the testdata, $n \le 10^4$. For all testdata, $1 \le n \le 10^5$ and $1 \le a_i \le 10^5$. # Input Format # Output Format Translated by ChatGPT 5