/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
長さ N の整数列 A_0,A_1,\cdots,A_{N-1} があります。 次式の値を求めてください。
- \sum_{i=0}^{N-2} \sum_{j=i+1}^{N-1} \mathrm{lcm}(A_i,A_j)
ここで、\mathrm{lcm}(x,y) は、x と y の最小公倍数を意味します。 なお、答えは非常に大きくなることがあるので、998244353 で割ったあまりを求めてください。
制約
- 1 \leq N \leq 200000
- 1 \leq A_i \leq 1000000
- 入力される値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
A_0\ A_1\ \cdots\ A_{N-1}
出力
\sum_{i=0}^{N-2} \sum_{j=i+1}^{N-1} \mathrm{lcm}(A_i,A_j) の値を 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
Score : 700 points
Problem Statement
We have an integer sequence of length N: A_0,A_1,\cdots,A_{N-1}.
Find the following sum (\mathrm{lcm}(a, b) denotes the least common multiple of a and b):
- \sum_{i=0}^{N-2} \sum_{j=i+1}^{N-1} \mathrm{lcm}(A_i,A_j)
Since the answer may be enormous, compute it modulo 998244353.
Constraints
- 1 \leq N \leq 200000
- 1 \leq A_i \leq 1000000
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
A_0\ A_1\ \cdots\ A_{N-1}
Output
Print the sum modulo 998244353.
Sample Input 1
3 2 4 6
Sample Output 1
22
\mathrm{lcm}(2,4)+\mathrm{lcm}(2,6)+\mathrm{lcm}(4,6)=4+6+12=22.
Sample Input 2
8 1 2 3 4 6 8 12 12
Sample Output 2
313
Sample Input 3
10 356822 296174 484500 710640 518322 888250 259161 609120 592348 713644
Sample Output 3
353891724