C - LCMs

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) は、xy の最小公倍数を意味します。 なお、答えは非常に大きくなることがあるので、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