[AdditionalFile2160.zip](file://AdditionalFile2160.zip?type=additional_file)

P3518 [POI 2011] SEJ-Strongbox

题目描述

有一个密码箱，$0$ 到 $n-1$ 中的某些整数是它的密码。且满足：若 $a$ 和 $b$ 是它的密码，则 $(a+b)\bmod n$ 也是它的密码（$a$，$b$ 可以相等）。某人试了 $k$ 次密码，前 $k-1$ 次都失败了，最后一次成功了。

问，该密码箱最多有多少种不同的密码。

输入格式

第一行两个整数 $n$，$k$。

第二行为 $k$ 个非负整数 $m_i$，表示每次试的密码。

输出格式

一行一个整数，表示答案。

输入输出样例 #1

输入 #1

42 5
28 31 10 38 24

输出 #1

14

说明/提示

数据规模与约定

对于约 $20\%$ 的数据，满足 $1\le k\le 100,n\le 10^{8}$。

对于约 $70\%$ 的数据，满足 $1\le k\le 1000$。

对于 $100\%$ 的数据，满足 $1\le k\le2.5\times10^5,k\le n\le 10^{14},0\le m<n$。

#2160. 「POI2011 R2」保险箱 Strongbox

标签: 传统 | 时间限制: 500 ms | 内存限制: 256 MiB |

题目描述

译自 POI 2011 Round 2. Day 0. A「Strongbox」

Byteasar 是一个有名的保险柜盗贼，但他最近宣布金盆洗手，并从事测试和认证防盗装置的工作。他刚刚收到一种新型保险柜并将要测试，这种保险柜是一种组合式保险柜，虽然都是用类似拨号盘的圆盘打开，但与一般组合保险柜有一些不同。拨号盘指针可以置于 $n$ 个不同的位置上，编号为 $0$ 到 $n-1$。将指针转至某些位置就能打开保险柜，转至其他位置就打不开。而对于这种组合式保险柜，如果指针转至 $x$ 和 $y$ 的时候能打开保险柜，那么转至 $(x+y)\bmod n$ 处也能打开保险柜。注意这里 $x=y$ 时也满足条件。

Byteasar 尝试了拨号盘上 $k$ 个不同的位置：$m_1,m_2,\ldots ,m_k$。当转至 $m_1, m_2, \ldots, m_{k - 1}$ 时，保险柜没有打开，只有转到 $m_k$ 时保险柜打开了。Byteasar 已经试了 $k$ 次，他已经不想继续试下去了。基于他已经试过的位置信息，他想知道最多可能有多少位置当指针转至此位置时能打开保险柜。请写一个程序帮助他解决这个问题。

输入格式

第一行两个整数 $n,k$；

接下来 $k$ 个不同的整数 $m_1,m_2,\ldots ,m_k$。

输出格式

输出一个整数，表示最后所求答案。

样例

输入

42 5
28 31 10 38 24

输出

14

数据范围与提示

对于全部数据，$1 \le k \le 250000, k \le n \le 10^{14}$。

对于 $70\%$ 的分数，保证 $k\le 1000$；

在这 $70\%$ 的分数中，有 $20\%$ 的分数保证 $n\le 10^8,k\le 100$。

Task author: Marian M. Kedzierski.