← 返回题目列表

AtCoder · pakencamp_2020_day1_k

K. 总和的 Gcd

中文机器翻译题面 查看原题
配点 : 500 点

問題文

企鹅人的长度N 序列 我有 A ,但它太大了,所以长度是 我决定将其压缩,使其变为 K 。

具体来说,A 的 K 连续子序列 B_1,\ B_2,\ldots,\ B_K ,然后创建一个新的 (B_1 中包含的元素总和 元素为),\ (B_2 中包含的元素总和 元素为),\ldots,\ (B_K 中包含的元素总和 元素为) 的序列 我决定生成 C 。

顺便说一下,penguinman 是一个特定的数字序列。 当你有 X 时,X 所有元素的最大公约数越大,你就会越快乐。

通过成功压缩数字序列,压缩后的数字序列 C 中元素的最大公约数是多少? 请解决

K=1,\ 2,\ \ldots,\ N 的这个问题。


制約

  • 所有输入均为整数。
  • 1\leq N\leq300
  • 1\leq A_i\leq300

入力

输入是按以下格式从标准输入给出的。 (10:38修正) 请输出超过

\(N\)
\(A_1\) \(A_2\) \(\ldots\) \(A_N\)

出力

N 行。 请在 i 在线 一个整数,表示住在 K=i 时输出答案。 请在末尾添加新行。

入力例1

3
1 2 3

出力例1

6
3
1

K=1 时,B_1=\{1,\ 2,\ 3\} 我别无选择,只能将其分开。压缩后的序列 C 表示 \{6\} 其最大公约数是 6 。 K=2 时,B_1=\{1,\ 2\},\ B_2=\{3\} 我应该把它分成 B_1=\{1\},\ B_2=\{2,\ 3\} 我应该将它与 2 有一条街。 压缩后的序列 C 分别是 \{3,\ 3\},\ \{1,\ 5\} 最大公约数是 3,\ 1 。前者具有最大值。 3 所以,3 。 K=3 时,B_1=\{1\},\ B_2=\{2\},\ B_3=\{3\} 我别无选择,只能将其分开。压缩后的序列 C 表示 \{1,\ 2,\ 3\} 其最大公约数是 1 。

入力例2

6
10 36 28 91 58 11

出力例2

234
3
2
2
1
1

入力例3

10
48 33 57 91 70 63 51 100 300 234

出力例3

1047
3
3
3
3
3
1
1
1
1