分数: 700 点
问题陈述
我们有一个长度为的整数序列 N: A_0,A_1,\cdots,A_{N-1}.
求以下总和 (\mathrm{lcm}(a, b) 表示最小公倍数 a 和 b):
- \sum_{i=0}^{N-2} \sum_{j=i+1}^{N-1} \mathrm{lcm}(A_i,A_j)
由于答案可能很大,请对其进行模计算 998244353.
约束
- 1 \leq N \leq 200000
- 1 \leq A_i \leq 1000000
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
A_0\ A_1\ \cdots\ A_{N-1}
输出
打印模数之和 998244353.
示例输入 1
3 2 4 6
示例输出 1
22
\mathrm{lcm}(2,4)+\mathrm{lcm}(2,6)+\mathrm{lcm}(4,6)=4+6+12=22.
示例输入 2
8 1 2 3 4 6 8 12 12
示例输出 2
313
示例输入 3
10 356822 296174 484500 710640 518322 888250 259161 609120 592348 713644
示例输出 3
353891724