#P3911. 最小公倍数之和

    ID: 2844 Type: RemoteJudge 1000ms 125MiB Tried: 4 Accepted: 3 Difficulty: 6 Uploaded By: Tags>数论数学莫比乌斯反演

最小公倍数之和

题目描述

对于A1,A2,,ANA_1,A_2,\cdots,A_N,求

i=1Nj=1Nlcm(Ai,Aj)\sum_{i=1}^N\sum_{j=1}^N \mathrm{lcm}(A_i,A_j)

的值。

lcm(a,b)\mathrm{lcm}(a,b) 表示 aabb 的最小公倍数。

输入格式

第一行,一个整数 NN

第二行,NN 个整数 A1,A2,,ANA_1,A_2,\cdots,A_N

输出格式

一行一个整数,表示所求的值。

2
2 3
17

提示

对于 30%30\% 的数据,1N10001 \le N \le 10001Ai5×1041 \le A_i \le 5\times 10^4

对于另外 30%30\% 的数据,1N5×1041 \le N \le 5\times 10^41Ai10001 \le A_i \le 1000

对于 100%100\% 的数据,1N5×1041 \le N \le 5\times 10^41Ai5×1041 \le A_i \le 5\times 10^4