/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
問題文
除夜の鐘の音が等間隔に N 回鳴りました。 より具体的には、鐘の音はある正整数 d と整数 t によって、 時刻 t, d+t, 2d+t, \ldots, (N-1)d+t と表される N 個の時刻それぞれに鳴りました。
高橋君は、そのうち時刻 A_1, A_2, \ldots, A_K に鳴った 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 としてあり得るものが少なくとも 1 つ存在する。
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \ldots A_K
出力
下記の形式にしたがって、正整数 d としてあり得るものすべてを昇順に列挙せよ。
M d_1 d_2 \ldots d_M
すなわち、まず 1 行目に、正整数 d としてあり得るものの個数 M を出力し、 2 行目に、正整数 d としてあり得るものすべてを昇順に並べた列 (d_1, d_2, \ldots, d_M) を空白区切りで出力せよ。
入力例 1
8 3 3 7 15
出力例 1
2 2 4
正整数 d としてあり得るものは、2 と 4 の 2 個です。
- d = 2 については、例えば時刻 3, 5, 7, 9, 11, 13, 15, 17 の 8 個の時刻に鐘の音が鳴ったという可能性が考えられます。
- d = 4 については、例えば時刻 -5, -1, 3, 7, 11, 15, 19, 23 の 8 個の時刻に鐘の音が鳴ったという可能性が考えられます。
入力例 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
Problem Statement
The New Year's bell rang N times at equal intervals. More specifically, the bell rang at times t, d+t, 2d+t, \ldots, (N-1)d+t for some positive integer d and integer t.
Takahashi heard the bell ring at times A_1, A_2, \ldots, A_K. Although it is certain that the bell actually rang when Takahashi heard the sound, the bell may have also rung at other times.
You are given N, K, and A_1, A_2, \ldots, A_K. List all possible values for the positive integer d in ascending order.
Under the constraints of this problem, it can be proved that the number of possible values for d is finite.
Constraints
- 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
- All input values are integers.
- There is at least one possible value for the positive integer d.
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \ldots A_K
Output
List all possible values for the positive integers d in ascending order in the following format:
M d_1 d_2 \ldots d_M
That is, the first line should contain M, the number of possible values for d, and the second line should contain (d_1, d_2, \ldots, d_M), all possible values for d in ascending order, with spaces in between.
Sample Input 1
8 3 3 7 15
Sample Output 1
2 2 4
There are two possible values for d: 2 and 4.
- For d = 2, it is possible that the bell rang eight times, for instance, at times 3, 5, 7, 9, 11, 13, 15, 17.
- For d = 4, it is possible that the bell rang eight times, for instance, at times -5, -1, 3, 7, 11, 15, 19, 23.
Sample Input 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
Sample Output 2
4 3 4 6 12