← 返回题目列表

AtCoder · agc038_c

C. 液晶模组

中文机器翻译题面 查看原题

分数: 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