AT_arc185_e [ARC185E] Adjacent GCD

[problemUrl]: https://atcoder.jp/contests/arc185/tasks/arc185_e 正整数列 $ 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 $ つの部分列が列として同じでも、取り出す位置が異なるならば区別するものとします。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

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

### 制約 - $ 1\ \leq\ N\ \leq\ 5\ \times\ 10^5 $ - $ 1\ \leq\ A_i\ \leq\ 10^5 $ - 入力される値は全て整数 ### Sample Explanation 1 $ 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 $ となります。