【题解】等差数列

欧几里得算法 —— 辗转相除法

1. a 和 b 的最大公约数等于 a 和 a % b 的最大公约数。
2. 证明 ：设 a = k * b + r ，则 a % b = r ；设 d 是 (a, a % b) 的公约数。那么有 d | b 和 d | r 均为 0 ，又因为 a = k * b + r ，所以 d | a 也为 0 ，可得对于 (a, a % b) 的任意公约数 d ，都有 d 是 (a, b) 的公约数。反之同样可以证明对于 (a, b) 的任意公约数 d 也是 (a, a % b) 的公约数。
3. 求 a 和 b 的最大公约数：int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } 。

最大公约数

1. 若等差数列所有项均相同，则最少需要的整数就是给出的整数。
2. 若差值不为 0 ，则项数为 (Amax - Amin)/Dmax + 1 。Amax 为序列中的最大项，Amin 为序列最小项。Dmax 为所有项与第一项的差值的最大公约数。

GCD C++ 531ms

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

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

int n;
int e[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 >> e[i];

    sort(e + 1, e + n + 1);
    int res = 0;
    for (int i = 2; i <= n; i ++ ) 
    {
        // 0 和任何数的最大公约数都是那个数本身
        res = gcd(res, e[i] - e[1]);
    }

    if (res == 0) cout << n;
    else cout << (e[n] - e[1]) / res + 1;

    system("pause");
    return 0;
}