题解

初始数字可以重复，但我们只关心不同数字组成的集合．操作只会增加数字，不会删除原数字．下面记初始最大值为 $M$．

先注意一个上界：两个不同正整数的差，一定比其中较大的数小．因此所有新数字都在 $1$ 到 $M$ 之间，最终最多有 $M$ 种数字．

算法 0：真的把所有正差加进去

用布尔数组记录哪些数字已经出现，再用一个数组保存已经出现的不同数字．依次取出数组中的数字，与它前面的所有数字做差；若得到未出现的正数，就标记并加到数组末尾．循环的终点随数组增长而增长，因此新数字也会被处理．

每一对不同数字都会在较晚加入的那个数被取出时检查一次．循环结束时，每一对数的正差都已存在，后续操作无法再加入任何新数，所以数组的长度就是答案．

最多出现 $M$ 个数字，共检查 $O(M^2)$ 对，连同读入的复杂度为 $O(n+M^2)$，空间复杂度为 $O(M)$．这里必须先去重，不能让大量重复卡片使模拟变成按卡片张数的平方枚举．

预期通过子任务 1，获得 20 分．验证用的独立暴力用集合去重，多一个 $\log M$ 因子，在本组范围内同样足够．

算法 1：已经有数字 1

如果 $a_1=1$，就可以用 $M$ 与 $1$ 得到 $M-1$，再用 $M-1$ 与 $1$ 得到 $M-2$，直到得到 $2$．连同已有的 $1$，所有 $1$ 到 $M$ 都能出现．结合开头的上界，答案恰好是 $M$．

注意不需要执行这么多次操作，只需扫描求最大值．时间复杂度 $O(n)$，额外空间复杂度 $O(1)$．

预期通过子任务 2，获得 10 分；和算法 0 合并，可以保证获得 30 分．

算法 2：最小的初始数字就是步长

设最小初始数字为 $v$，并且所有初始数字都是 $v$ 的倍数．

两个 $v$ 的倍数相减，仍然是 $v$ 的倍数，所以不会得到 $v,2v,\ldots,M$ 之外的正数．另一方面，$v$ 已经存在，可以从 $M$ 开始反复减去 $v$，得到上面所有倍数．答案因此为 $M/v$．

这里不要求最小值位于第一个位置，也不要求初始数字不同．扫描数组找到最小值和最大值即可，时间复杂度 $O(n)$，额外空间复杂度 $O(1)$．

预期通过子任务 2、3，获得 30 分；和算法 0 合并，可以保证获得 50 分．

算法 3：只有一张或两张卡片

只有一个数字时不能产生新数，答案为 $1$．

考虑两个不同数字 $x<y$．用 $x$ 从 $y$ 中不断相减，相当于把较大的数缩小．如果 $y$ 不是 $x$ 的倍数，会得到正余数 $y\bmod x$；若能整除，则当前较小的数 $x$ 已经可以作为步长．继续对较小的数与非零余数做同样的事，就是欧几里得算法．

这个过程能制造出 $g=\gcd(x,y)$．初始最大值一直保留，因此之后可以从最大值不断减去 $g$，得到其下所有正倍数．又因为初始数字及其差都是 $g$ 的倍数，答案为 $\max(x,y)/g$．

程序中使用取模跳过重复相减，时间复杂度 $O(\log M)$，额外空间复杂度 $O(1)$．不要真的减上亿次．

预期通过子任务 4，获得 20 分；把前面四种方法合并，可以保证获得 70 分．各子任务独立计分，不要求先通过其他子任务．

算法 4：这个步长到底是什么

一般情况下，最小的初始数字不一定是最后的步长．例如初始数字为 $6,10$，新产生的 $4$ 还能与 $6$ 产生 $2$．所以不能直接用最大值除以初始最小值．

设所有初始数字的最大公约数为 $g$．先证明任何时候都只有 $g$ 的倍数：开始时成立；若 $x,y$ 都是 $g$ 的倍数，$|x-y|$ 也一定是．因此最终的数字只能来自

还需要证明这些数都能造出来，仅有这个上界不够．

只要还存在未出现的正差，就把它加进来．由于每次至少多一种数字，且只有 $M$ 个候选数，这个过程会停止．此时得到的集合对正差封闭：任意两个不同数字的差都已在集合里．

设此时最小的正数为 $d$．如果集合中某个数 $x$ 不能被 $d$ 整除，反复从 $x$ 减去 $d$，最终会得到 $1$ 到 $d-1$ 之间的正余数．这些相减都是合法操作，余数也必须在集合内，与 $d$ 最小矛盾．所以 $d$ 能整除集合中的每一个数，尤其能整除所有初始数字，即 $d$ 是它们的公约数，有 $d\le g$．

另一方面，$d$ 也是操作得到的数，前面证明过它必然是 $g$ 的正倍数，因此 $d\ge g$．两边合起来，得到 $d=g$．

既然数字 $g$ 已经存在，便可以从仍保留着的 $M$ 出发，不断减去 $g$，得到所有 $g$ 的正倍数．因此答案恰好是

读入时维护最大值和当前所有数字的 gcd，不需要真的制作卡片，也不需要存整个数组．令初始 gcd 为 $0$，利用 $\gcd(0,x)=x$，可以自然处理第一项、单个数字和全部相等的情况．

每次欧几里得算法耗时 $O(\log M)$，总时间复杂度为 $O(n\log M)$，额外空间复杂度为 $O(1)$．答案不超过 $10^9$，本题使用 int 足够．

预期通过全部子任务，获得 100 分．

参考代码

#include <algorithm>
#include <iostream>
using namespace std;
int gcd(int a, int b) {
    while (b) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int g = 0, mx = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        g = gcd(g, x);
        mx = max(mx, x);
    }
    cout << mx / g << '\n';
    return 0;
}