← 返回题目列表

AtCoder · arc185_e

E. 相邻 GCD

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

定义 分数 游戏的 正整数序列 B = (B_1, B_2, \dots, B_k) as \displaystyle \sum_{i=1}^{k-1} \gcd(B_i, B_{i+1}).
给定一个正整数序列 A = (A_1, A_2, \dots, A_N),解决以下问题 m = 1, 2, \dots, N.

  • 有 2^m - 1 序列的非空子序列 (A_1, A_2, \dots, A_m)。求所有这些子序列的分数总和,模 998244353。如果两个子序列取自序列中的不同位置,则即使它们作为序列一致,也可以区分它们。

约束

  • 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 is 0 + 0 + 0 + 3 + 1 + 2 + 5 = 11.


示例输入 2

5
3 8 12 6 9

示例输出 2

0
1
13
57
155

示例输入 3

10
47718 21994 74148 76721 98917 73766 29598 59035 69293 29127

示例输出 3

0
2
14
35
97
372
866
1859
4273
43287