P4661 等差数列（基础）

解题思路

第一步，读懂题目。 小明记得 N 个数，想找出包含这些数的最短等差数列有几项。比如给了 2、6、4、10、20 五个数，排序后是 2、4、6、10、20。

第二步，找到公差。 它们相邻的差分别是 2、2、4、10，这些差值的最大公约数是 2，所以公差是 2。最短数列就是从 2 到 20 每隔 2 取一个：2、4、6、8、10、12、14、16、18、20，一共 10 项。

第三步，想一想生活里的例子。 楼梯每一级高度相同才叫楼梯。如果几块砖要放在同一段楼梯上，它们的高度差必须都是某个"基本步长"的整数倍。这个基本步长（公差）取所有相邻差的"最大公约数"，就能保证所有数都落在台阶上，而且台阶数最少。

第四步，写出公式。 先把 N 个数从小到大排序，然后求所有相邻两个数的差的最大公约数 commonDiff，答案就是 (最大值 - 最小值) / commonDiff + 1。求最大公约数用辗转相除法，写成一个 gcd 函数反复调用。

第五步，想一想为什么公式正确。 最短等差数列从最小值开始，每隔公差跳一次，一直跳到最大值。最小值到最大值之间有 (最大值-最小值)/公差 个间隔，项数 = 间隔数 + 1。比如 2 到 20、公差 2，间隔是 (20-2)/2=9 个，项数就是 9+1=10 项，正好对应 2、4、6、8、10、12、14、16、18、20 这 10 个数。

第六步，注意几个特殊情况。 如果所有数都相等，题目提示直接输出 N，因为这时相邻差都是 0，没法求公约数。如果 N=1，只有一个数，它自己就是一个长度 1 的等差数列，答案就是 1。还要注意 N 最大到 1000000，排序要用快的算法（比如快速排序）；数的范围在 int 内，但答案可能超过 int，要用 long long 存。

参考代码

// P4661 等差数列：排序后相邻差值求最大公约数为公差，最短项数=(最大-最小)/公差+1
#include <iostream>
#include <algorithm>

long long gcd(long long a, long long b) {
    while (b) {
        long long remainder = a % b;
        a = b;
        b = remainder;
    }
    return a;
}

int num[1000005];

int main() {
    std::ios::sync_with_stdio(false);
    int n;
    std::cin >> n;
    for (int i = 0; i < n; i++) std::cin >> num[i];
    std::sort(num, num + n);
    // 所有数相等时，最短数列就只有这 n 项
    if (num[0] == num[n - 1]) {
        std::cout << n << "\n";
        return 0;
    }
    // 公差是所有相邻差值的最大公约数
    long long commonDiff = 0;
    for (int i = 1; i < n; i++) commonDiff = gcd(commonDiff, (long long)num[i] - num[i - 1]);
    long long answer = ((long long)num[n - 1] - num[0]) / commonDiff + 1;
    std::cout << answer << "\n";
    return 0;
}

复杂度分析

排序需要 O(N log N) 的时间，N 最大 1000000，完全没问题。求相邻差的最大公约数需要 O(N) 次辗转相除，每次很快。整体时间复杂度 O(N log N)。空间上需要一个 N 大小的数组，约 4MB。答案用 long long 防止溢出，是这道题需要注意的小细节。