封闭性：a \in G, b \in G \Rightarrow a+b \mod n\in G， 这是已知条件
结合性：(a + b) + c = a + (b + c) \mod n
单位元：如果 a \in G
\Rightarrow 2*a \mod n \in G\Rightarrow 3*a \mod n \in G \Rightarrow ... \Rightarrow n*a \mod n \in G
而 $0$ 满足性质 $a + 0 = 0 + a \mod n$，所以 $0$ 就是 $(G,+)$ 的单位元。
逆元：假设 $a \in G$，现在我们来寻找 $a$的逆元，由于 $a + (n-1)*a = n*a = 0 \mod n$，并且 $(n-1)*a + a = n*a = 0 \mod n$，所以对任意元素 $a$，都存在一个逆元，为$(n-1)*a \mod n
由上可知，(G,+)是一个群。
由于逆元的存在，使得如果 a \in G，那么 -a \in G，这里的 -a 并不是一个真的负数， -a指的是 a 的逆元。为了表述方便，以下的加减乘运算也都是模n意义下的。显然如果 a \in G, b \in G \Rightarrow a - b = a + (-b) \mod n \in G。
推论一：如果 a \in G, b \in G，那么 gcd(a, b) \in G
证明：由群的封闭性可知
a \in G \Rightarrow x*a \in G$，其中 $x$ 为任意整数 $(1)b \in G \Rightarrow y*b \in G$，其中 $y$ 为任意整数 $(2)
由于有逆元的存在，上述的系数 x,y 可以为负数。
结合(1),(2)可知，x*a + y*b \in G，所以 gcd(a, b) \in G
推论二：如果 a \in G，那么 gcd(n, a) \in G
证明：
不妨设 n = a*k + r，其中 k 和 r 都是整数，并且 r < a，由数论知识可知
gcd(n, a) = gcd(a, r)a \in G \Rightarrow (k+1)*a \in G \Rightarrow a*k + a \in G \Rightarrow n - r + a \in G
$ \Rightarrow r \in G \Rightarrow gcd(a, r) \in G \Rightarrow gcd(n, a) \in G
推论三：G 是一个循环群，假设 G 中最小非零元素为 g，那么集合 G = \{ 0,g,2*g,3*g,... \}
证明：
(1) 对集合 G 中的任意一个元素 x， 由推论二可知 gcd(x, g) \in G，由于g 是最小的元素，所以 g \leq gcd(g, x) \leq g，所以 g = gcd(g,x)，所以 g 一定能被 x 整除，换而言之 g 一定可以整除集合 G 中的任意一个元素。
(2) 因为 g \in G \Rightarrow 2*g \in G \Rightarrow 3*g \in G \Rightarrow ... \Rightarrow g 的任意整数倍模 n 都在 G 中。当然单位元 0 也在 G 中。
结合(1)(2)可知，G 是一个循环群
推论四：假设 G 中最小非零元素为 g，那么 g 可以被 n 整除，并且 G 中元素个数 |G| = n/g
证明：
由于 g \in G，由推论二可知 gcd(n, g) \in G，又由于 g 是最小的非零元素，所以 g \leq gcd(n, g) \leq g，所以 g = gcd(n, g)，g 可以被 n 整除。
由于题目中要求 G 中最大元素小于 n，结合推论三可知，G 中最大的元素为 n - g。|G| = (n-g)/g + 1 = n/g
下面回到题目本身，由推论三可知，只要我们确定了生成元 g，那么集合 G就确定了，下面我们来寻找符合条件的 g。由于前 k-1 次尝试没有打开锁，所以前 k-1 次尝试的数字一定不在集合 G 中。由推论三可知: m_1, m_2, ... m_{k-1}一定都不能被 g 整除。而结合推论四可知： n 和 m_k 都可以被 g 整除，所以gcd(n, m_k) 可以被 g 整除。 题目要求让 |G| 最大，只需要找到最小的 g 满足这个约束条件即可。
可以先计算 gcd(n, m_k)，然后从1开始往上遍历筛选符合条件的 g
代码如下：
#include <stdio.h>
#define SIZE 250000
long long a[SIZE];
long long gcd(long long x, long long y) {
long long t = 0;
while (y != 0) {
t = x;
x = y;
y = t % y;
}
return x;
}
int is_valid(long long x, int k) {
int i;
for (i = k - 1; i >= 0; i--) {
if (a[i] % x == 0) {
return 0;
}
}
return 1;
}
int main() {
long long n, k, b;
long long i, j, len = 0;
scanf("%lld%lld", &n, &k);
k--;
for (i = 0; i <= k; i++) {
scanf("%lld", &a[i]);
}
a[k] = gcd(a[k], n);
long long r = 0;
long long g = 0;
for (g = 1; g <= a[k] / g; g++) {
if (a[k] % g != 0) {
continue;
}
if (is_valid(g, k)) {
printf("%lld\n", n / g);
return 0;
} else if (is_valid(a[k] / g, k)) {
r = n / a[k] * g;
}
}
printf("%lld\n", r);
return 0;
}