这一次，我们将回归初中数学，具体是七年级/八年级代数中的 “等差数列”（Arithmetic Sequence）以及 “公约数”（GCD）的概念。

这道题目考察的是排序（Sorting）、辗转相除法求最大公约数（GCD）以及数学推导能力。难度定位 GESP 5级（CSP-J T2 难度）。

---

题目：残缺的等差数列 (The Broken Arithmetic Sequence)

【背景知识讲解】

在初中数学中，我们学习了等差数列的概念： 如果一个数列从第二项起，每一项与它的前一项的差等于同一个常数，这个数列就叫做等差数列。这个常数叫做等差数列的公差，通常用字母 $d$ 表示。

通项公式： 若首项为 $a_1$，公差为 $d$，则第 $n$ 项 $a_n$ 为：

$$a_n = a_1 + (n-1)d$$

性质：

1. 对于数列中的任意两项 $a_i$ 和 $a_j$ ($i < j$)，它们之间的差一定是公差 $d$ 的倍数。即：$a_j - a_i = (j-i) \times d$。
2. 数列的总项数 $n$ 可以通过首项、末项和公差求出：$n = \frac{a_n - a_1}{d} + 1$。

【题目描述】

老师在黑板上写下了一个正整数等差数列。 然而，值日生在擦黑板时，不小心擦掉了一些数字，只留下了 $N$ 个数字。 幸运的是，剩下的这 $N$ 个数字并没有改变它们原本的数值，只是原本在它们中间的一些数字不见了。

现在给出了这幸存的 $N$ 个整数。假设原本的数列是一个项数最少的等差数列。 请你计算：原本的等差数列一共有多少项？

注意：

1. 输入的数据顺序可能是乱的。
2. 原本数列的公差 $d > 0$（即数列是严格递增的）。如果输入的数字全部相同，则认为公差 $d=0$（此时项数就是 $N$）。

【输入格式】

第一行包含一个整数 $N$，表示幸存数字的个数。 第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$，表示幸存的这些数字。

【输出格式】

输出一个整数，表示原本等差数列的最少项数。

【样例数据】

输入：

5
2 6 4 10 20

输出：

10

样例解释：

1. 排序：首先整理幸存的数字：2, 4, 6, 10, 20。
2. 观察差值：
   • 4 - 2 = 2
   • 6 - 4 = 2
   • 10 - 6 = 4
   • 20 - 10 = 10
   • 相邻差值集合为 $\{2, 2, 4, 10\}$。
3. 推导公差：
   • 原本的公差 $d$ 必须能同时整除所有的相邻差值。
   • 为了使项数最少，$d$ 应该尽可能大。
   • 所以 $d = \text{GCD}(2, 4, 10) = 2$。
4. 还原数列：
   • 以 2 为首项，20 为末项，公差为 2。
   • 数列为：2, 4, 6, 8, 10, 12, 14, 16, 18, 20。
   • 总项数 = $(20 - 2) / 2 + 1 = 10$。

【数据范围】

• 对于 100% 的数据：$2 \le N \le 100,000$。
• $0 \le A_i \le 1,000,000,000$（$10^9$）。
• 保证输入数字不完全相同（即至少有两个不同的数，除非 $N=1$，但数据范围保证 $N \ge 2$）。
• 修正：如果输入的数字全部相同，输出 $N$。

---

一、 思路提示

1. 有序化：
   • 等差数列的定义是基于“顺序”的。给出的数组是乱序的，第一步必须排序（Sort），设排序后的数组为 $A$。
2. 寻找公差 $d$：
   • 排序后，我们计算相邻两项的差值：$\Delta_1 = A_2 - A_1$，$\Delta_2 = A_3 - A_2, \dots$。
   • 原本的公差 $d$ 必须是所有 $\Delta_i$ 的公约数。
   • 题目要求“项数最少” $\rightarrow$ 这意味着公差 $d$ 要尽可能大（步子迈得越大，走完同样距离所需的步数越少）。
   • 所以，目标公差 $d$ 就是所有相邻差值的最大公约数（Greatest Common Divisor, GCD）。
3. 特殊情况：
   • 如果所有数字都一样（比如 5 5 5），差值全为 0。GCD(0, 0) 通常无定义或为 0。在这种情况下，公差 $d=0$，项数就是 $N$。
4. 公式计算：
   • 求出 $d$ 后，项数 $= \frac{A_N - A_1}{d} + 1$。

---

二、 预备知识点总结

1. 排序：std::sort，复杂度 $O(N \log N)$。
2. 最大公约数 (GCD)：
   • 欧几里得算法（辗转相除法）：gcd(a, b) = gcd(b, a % b)。
   • 多个数的 GCD：gcd(a, b, c) = gcd(a, gcd(b, c))。
   • C++14/17 标准库内置 std::__gcd 或 <numeric> 中的 std::gcd。
3. 数学逻辑：等差数列通项公式的逆运算。

---

三、 启发式教学：草稿纸上的推理过程

教练：“同学们，假设你在地上捡到了一把断掉的尺子，上面只剩下几个刻度：30, 45, 60。请问这把尺子原本最小的刻度单位是多少？”

1. 排序：已经是有序的了：30, 45, 60。
2. 看间距：
   • 30 到 45，距离 15。
   • 45 到 60，距离 15。
   • “看来刻度单位是 15？这把尺子可能是 30, 45, 60。”

教练：“那如果捡到的刻度是 3, 9, 15, 23 呢？哦，23不是等差的，换一个：2, 6, 12。”

1. 排序：2, 6, 12。
2. 看间距：
   • 2 到 6，距离 4。
   • 6 到 12，距离 6。
   • “刻度单位可以是 4 吗？”
   • “不行，如果是 4，6 后面应该是 10，然后 14。得不到 12。”
   • “刻度单位可以是 6 吗？”
   • “不行，如果是 6，2 后面应该是 8。得不到 6。”
   • “那这个单位（公差）必须既能走完 4，又能走完 6。”
   • 结论：公差必须是 4 和 6 的公约数。要项数最少 $\rightarrow$ 最大公约数 GCD(4, 6) = 2。
3. 验证：
   • 以 2 为单位：2, 4, 6, 8, 10, 12。
   • 包含题目给的 2, 6, 12。没问题。
   • 项数 = $(12 - 2) / 2 + 1 = 6$。

教练：“所以，我们的算法就是：先排序，求所有相邻差值，算出它们的最大公约数，最后套公式。”

---

四、 读题关键词总结

1. “等差数列” $\rightarrow$ 核心模型。
2. “项数最少” $\rightarrow$ 意味着公差 $d$ 最大 $\rightarrow$ 求 GCD。
3. “输入乱序” $\rightarrow$ 必须 Sort。
4. “正整数” / $10^9$ $\rightarrow$ 使用 int 足够（差值最大 $10^9$），但计算结果可能稍大（虽然本题项数不会超过 $10^9$，但在中间计算时注意溢出风险，不过本题不用担心乘法）。

---

五、 标准题解代码 (C++14)

见题解

这道题目将 初中代数（等差数列） 与 数论算法（GCD） 完美结合。虽然代码量不大，但逻辑性强，要求学生理解“差分的公约数即为原公差”这一数学本质，非常适合 GESP 5 级的考察目标。