P0789

[Poi2011]Strongbox

密码箱的旋钮共有 nn 个位置，编号为 00 到 n−1n-1。其中一些位置可以打开密码箱，并满足如下性质：如果位置 aa 和 bb 都能打开密码箱，那么位置 (a+b) mod n(a+b)\bmod n 也能打开密码箱，其中 aa 与 bb 可以相等。

Byteasar 依次尝试了 kk 个互不相同的位置 m1,m2,…,mkm_1,m_2,\ldots,m_k。前 k−1k-1 次尝试均未能打开密码箱，只有最后尝试的位置 mkm_k 成功打开了密码箱。

在所有与这些尝试结果相符的密码箱中，请求出能够打开密码箱的位置数量的最大值。

输入格式

第一行包含两个整数 nn 和 kk，分别表示旋钮位置的总数和尝试次数。

第二行包含 kk 个互不相同的整数 m1,m2,…,mkm_1,m_2,\ldots,m_k，依次表示每次尝试的位置。

保证输入数据对应至少一种满足题目条件的密码箱。

输出格式

输出一个整数，表示能够打开密码箱的位置数量的最大值。

样例输入

42 5
28 31 10 38 24

样例输出

14

数据范围

  • 1≤k≤2.5×1051\le k\le 2.5\times 10^5；
  • k≤n≤1014k\le n\le 10^{14}；
  • 对于所有 1≤i≤k1\le i\le k，均有 0≤mi<n0\le m_i<n；
  • m1,m2,…,mkm_1,m_2,\ldots,m_k 两两不同；
  • 约 70%70\% 的测试数据满足 k≤103k\le 10^3；
  • 约 20%20\% 的测试数据还满足 n<108n<10^8 且 k≤100k\le 100；
  • 时间限制为 3×104 ms3\times 10^4\ \mathrm{ms}；
  • 内存限制为 3.2768×104 KB3.2768\times 10^4\ \mathrm{KB}。

来源与许可

本题为 POI 2011 试题「Strongbox」，题面与测试数据整理自 BZOJ 2277。