Problem : 158 - 猜密碼

Problem Statistics

Solved Member: 6　　Submission: 16　　User Tried: 6

Statement:

你把你所有的 heuristic game 藏到保險箱裡，並鎖上了密碼。不幸的是，某天當你想玩的時候卻忘記了。

你只好請來世界上最強的破解專家來測試，保險箱有一個轉盤，有 n 個位置，分別由 0 標號到 n-1，可能有許多個在 0 到 n-1 之間的密碼。若 x 和 y 都是密碼，你發現從 x 往右轉 y 格也是密碼，意即第 (x+y) mod n 格也是密碼。

專家做了 k 次嘗試，前 k-1 次嘗試到錯的密碼，只有第 k 次猜的密碼是對的。你記下了他這 k 次所猜的數字，你想知道究竟最多可能有多少種密碼。

Input:Output:

第一行有兩個數字 n(k ≤ n ≤ 10^14),k(1 ≤ k ≤ 250000)。
第二行有 k 個數字，代表每一次專家猜測的密碼，每次猜測的密碼皆在 0 到 n-1 之間，且沒有重複。

請輸出一個數字，代表最多可能有幾種密碼。

Sample Input:Sample Output:

42 5
28 31 10 38 24

Source:

POI 18 Stage 2

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	3000ms	32768kb
1-ocen	3000ms	32768kb
1-1	3000ms	32768kb	7
1-2	3000ms	32768kb
1-3	3000ms	32768kb
1-4	3000ms	32768kb
2-ocen	3000ms	32768kb
2-1	3000ms	32768kb	7
2-2	3000ms	32768kb
2-3	3000ms	32768kb
3-ocen	3000ms	32768kb
3-1	3000ms	32768kb	7
3-2	3000ms	32768kb
3-3	3000ms	32768kb
4-ocen	3000ms	32768kb
4-1	3000ms	32768kb	7
4-2	3000ms	32768kb
4-3	3000ms	32768kb
5-1	3000ms	32768kb	7
5-2	3000ms	32768kb
5-3	3000ms	32768kb
5-4	3000ms	32768kb
6-1	3000ms	32768kb	7
6-2	3000ms	32768kb
6-3	3000ms	32768kb
6-4	3000ms	32768kb
7-1	3000ms	32768kb	7
7-2	3000ms	32768kb
7-3	3000ms	32768kb
7-4	3000ms	32768kb
8-1	3000ms	32768kb	7
8-2	3000ms	32768kb
8-3	3000ms	32768kb
8-4	3000ms	32768kb
9-1	3000ms	32768kb	7
9-2	3000ms	32768kb
9-3	3000ms	32768kb
9-4	3000ms	32768kb
10-1	3000ms	32768kb	7
10-2	3000ms	32768kb
10-3	3000ms	32768kb
10-4	3000ms	32768kb
11-1	5000ms	32768kb	7
11-2	5000ms	32768kb
11-3	5000ms	32768kb
11-4	5000ms	32768kb
11-5	5000ms	32768kb
12-1	5000ms	32768kb	7
12-2	5000ms	32768kb
12-3	5000ms	32768kb
12-4	5000ms	32768kb
12-5	5000ms	32768kb
13-1	5000ms	32768kb	8
13-2	5000ms	32768kb
13-3	5000ms	32768kb
13-4	5000ms	32768kb
13-5	5000ms	32768kb
14-1	5000ms	32768kb	8
14-2	5000ms	32768kb
14-3	5000ms	32768kb
14-4	5000ms	32768kb
14-5	5000ms	32768kb