分数: 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