题目描述

数学老师给小明出了一道等差数列求和的题目。

但是粗心的小明忘记了一部分的数列，只记得其中N个整数。

现在给出这N个整数，小明想知道包含这N个整数的最短的等差数列有几项？

样例

输入数据

5
2 6 4 10 20

输出数据

10 

(最大公约数gcd) $O(nlogn)$

等差数列的特点是，数列的所有元素与最小元素之间的差，应该是公差d的倍数。因此，所有的差值 w[i] − w[1] （这里的 w[1] 是最小值）必须是公差 d 的倍数。
所以，要求出一个合适的公差 d，我们需要找出这些差值之间的最大公约数。
换句话说，所有 w[i] − w[1] 的差值的最大公约数就是这个等差数列的公差。

C++ 代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+10;

typedef long long ll;
int w[N];
int d = 0;
int 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 >> w[i];
    sort(w + 1, w + 1 + n);

    for(int i = 2; i <= n; i ++)
        d = gcd(d, w[i] - w[1]);

     if(d == 0)
     {
          cout<<n<<endl;
          return 0;
     }
     cout <<1 + (w[n] - w[1]) / d <<endl;
    return 0;
}