GCDDCG

시간 제한1초메모리 제한2048 MB

요약

각 라운드 i에서 두 덱의 최대공약수가 모두 i가 되도록 겹치지 않는 비어 있지 않은 덱 두 개를 고르는 경우의 수를 구합니다. 그 수에 i를 곱해 전부 더한 값을 998244353으로 나눈 나머지를 출력합니다.

난이도: 보통10점 중 5점
유형: 수학
정답자: 아직 제출이 없습니다

문제

최대공약수 덱 구성 카드 게임(GCDDCG)을 하고 있다. 카드는 1번부터 N번까지 N장이 있고, 카드 i의 값은 $A_i$ 이다. $A_i$ 는 1 이상 N 이하의 정수이다.

게임은 1번부터 N번까지 N개의 라운드로 진행된다. 각 라운드에서는 덱 1과 덱 2, 두 개의 비어 있지 않은 덱을 만든다. 한 카드가 두 덱에 동시에 들어갈 수 없고, N장을 모두 사용하지 않아도 된다. 라운드 i에서 각 덱에 있는 카드 값의 최대공약수(GCD)는 반드시 i와 같아야 한다.

라운드 i의 창의성 점수는 i와 유효한 덱 두 개를 만드는 방법의 수를 곱한 값이다. 한쪽 덱에 들어가는 카드가 다르면 서로 다른 방법으로 센다.

모든 라운드의 창의성 점수 합을 구하라. 합이 매우 클 수 있으므로 $998\,244\,353$ 으로 나눈 나머지를 출력한다.

입력

첫째 줄에 정수 N ( $2 \le N \le 200\,000$ )이 주어진다.

둘째 줄에 N개의 정수 $A_i$ ( $1 \le A_i \le N$ )가 주어진다.

출력

모든 라운드의 창의성 점수 합을 $998\,244\,353$ 으로 나눈 나머지를 한 줄에 출력한다.

예제3

예제 1
입력
```
3
3 3 3
```
예상 출력
```
36
```
예제 2
입력
```
4
2 2 4 4
```
예상 출력
```
44
```
예제 3
입력
```
9
4 2 6 9 7 7 7 3 3
```
예상 출력
```
10858
```