← 返回题目列表

AtCoder · past202309_j

J. 除夕钟声

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

问题陈述

新年的钟声敲响了 等间隔 N 次。 更具体地说,铃声有时会响起 t, d+t, 2d+t, \ldots, (N-1)d+t 对于某个正整数 d 和整数 给出了 t.

高桥有时听到铃声响起 A_1, A_2, \ldots, A_K。 虽然可以肯定的是,当高桥听到声音时,铃声确实响了,但铃声可能在其他时候也响过。

你被给予 N, K,和 A_1, A_2, \ldots, A_K。 列出正整数的所有可能值 d 按升序排列.

在这个问题的约束下,可以证明,可能值的个数 d 是有限的。

约束

  • 2 \leq N \leq 10^9
  • 2 \leq K \leq \min \lbrace N, 2 \times 10^5 \rbrace
  • 0 \leq A_1 \lt A_2 \lt \cdots \lt A_K \leq 10^9
  • 所有输入值均为整数。
  • 正整数至少有一个可能的值 d.

输入

输入由标准输入按以下格式给出:

N K
A_1 A_2 \ldots A_K

输出

列出正整数的所有可能值 d 按以下格式升序排列:

M
d_1 d_2 \ldots d_M

也就是说,第一行应包含 M,可能值的数量 d, 第二行应包含 (d_1, d_2, \ldots, d_M),所有可能的值 d 按升序排列,中间有空格。


示例输入 1

8 3
3 7 15

示例输出 1

2
2 4

有两个可能的值 d: 2 和 4.

  • 对于 d = 2,例如,有时铃声可能会响八次 3, 5, 7, 9, 11, 13, 15, 17.
  • 对于 d = 4,例如,有时铃声可能会响八次 -5, -1, 3, 7, 11, 15, 19, 23.

示例输入 2

500 22
30 42 138 318 354 378 450 462 522 582 630 738 834 894 930 942 1002 1050 1062 1110 1146 1158

示例输出 2

4
3 4 6 12