E - Adjacent GCD

Contest Duration: 2024-10-13 21:00:00+0900 - 2024-10-13 23:00:00+0900 (local time) (120 minutes) Back to Home

E - Adjacent GCD Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

正整数列 B = (B_1, B_2, \dots, B_k) の スコア を \displaystyle \sum_{i=1}^{k-1} \gcd(B_i, B_{i+1}) として定義します。
長さ N の正整数列 A = (A_1, A_2, \dots, A_N) が与えられるので、m = 1, 2, \dots, N に対して次の問題を解いてください。

列 (A_1, A_2, \dots, A_m) の空でない部分列は 2^m - 1 通りありますが、それらのスコアの総和を 998244353 で割った余りを求めてください。ただし、2 つの部分列が列として同じでも、取り出す位置が異なるならば区別するものとします。

制約

1 \leq N \leq 5 \times 10^5
1 \leq A_i \leq 10^5
入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \dots A_N

出力

N 行出力せよ。i 行目には m = i の時の答えを出力せよ。

入力例 1

3
9 6 4

出力例 1

0
3
11

m = 3 の時を考えます。(A_1, A_2, A_3) = (9, 6, 4) の空でない部分列、およびそのスコアを列挙すると次のようになります。

(9) : スコアは 0 です。
(6) : スコアは 0 です。
(4) : スコアは 0 です。
(9, 6) : スコアは \gcd(9, 6) = 3 です。
(9, 4) : スコアは \gcd(9, 4) = 1 です。
(6, 4) : スコアは \gcd(6, 4) = 2 です。
(9, 6, 4) : スコアは \gcd(9, 6) + \gcd(6, 4) = 3 + 2 = 5 です。

以上より、m = 3 の時の答えは 0 + 0 + 0 + 3 + 1 + 2 + 5 = 11 となります。

入力例 2

5
3 8 12 6 9

出力例 2

入力例 3

10
47718 21994 74148 76721 98917 73766 29598 59035 69293 29127

出力例 3

Score : 800 points

Problem Statement

Define the score of a sequence of positive integers B = (B_1, B_2, \dots, B_k) as \displaystyle \sum_{i=1}^{k-1} \gcd(B_i, B_{i+1}).
Given a sequence of positive integers A = (A_1, A_2, \dots, A_N), solve the following problem for m = 1, 2, \dots, N.

There are 2^m - 1 non-empty subsequences of the sequence (A_1, A_2, \dots, A_m). Find the sum of the scores of all those subsequences, modulo 998244353. Two subsequences are distinguished if they are taken from different positions in the sequence, even if they coincide as sequences.

Constraints

1 \leq N \leq 5 \times 10^5
1 \leq A_i \leq 10^5
All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Print N lines. The i-th line should contain the answer for m = i.

Sample Input 1

3
9 6 4

Sample Output 1

0
3
11

Consider the case m = 3. Here are the non-empty subsequences of (A_1, A_2, A_3) = (9, 6, 4) and their scores.

(9): Score is 0.
(6): Score is 0.
(4): Score is 0.
(9, 6): Score is \gcd(9, 6) = 3.
(9, 4): Score is \gcd(9, 4) = 1.
(6, 4): Score is \gcd(6, 4) = 2.
(9, 6, 4): Score is \gcd(9, 6) + \gcd(6, 4) = 3 + 2 = 5.

Therefore, the answer for m = 3 is 0 + 0 + 0 + 3 + 1 + 2 + 5 = 11.

Sample Input 2

5
3 8 12 6 9

Sample Output 2

Sample Input 3

10
47718 21994 74148 76721 98917 73766 29598 59035 69293 29127

Sample Output 3