C++

$\color{gold}{— > 蓝桥杯辅导课题解}$

思路：

贪心

$等差数列： a_n = a_1 + (n - 1)d$

$每一项与第一项的差一定是公差d的倍数，由此，求一下公差即可$

$时间复杂度：O(nlog_2n)$

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 1e5 + 10;

int n;
int a[N];

int gcd(int a, int b) { // 求最大公约数
    return b ? gcd(b, a % b) : a;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    sort(a + 1, a + n + 1);

    int d = 0;
    for (int i = 2; i <= n; i ++) 
        d = gcd(d, a[i] - a[1]); // 确定公差

    if (!d) cout << n; 
    else cout << (a[n] - a[1]) / d + 1;

    return 0;
}