P3911 Sum of Least Common Multiples

For $A_1, A_2, \cdots, A_N$, compute the following value. $\sum_{i=1}^N\sum_{j=1}^N \mathrm{lcm}(A_i,A_j)$ Here, $\mathrm{lcm}(a, b)$ denotes the least common multiple of $a$ and $b$.

The first line contains an integer $N$. The second line contains $N$ integers $A_1, A_2, \cdots, A_N$.

Output one integer in a single line, representing the required value.

Constraints: - For 30% of the testdata, $1 \le N \le 1000$, $1 \le A_i \le 5 \times 10^4$. - For another 30% of the testdata, $1 \le N \le 5 \times 10^4$, $1 \le A_i \le 1000$. - For 100% of the testdata, $1 \le N \le 5 \times 10^4$, $1 \le A_i \le 5 \times 10^4$. Translated by ChatGPT 5