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

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

个整数。

现在给出这 N
个整数，小明想知道包含这 N

个整数的最短的等差数列有几项？
输入格式

输入的第一行包含一个整数 N

。

第二行包含 N
个整数 A1,A2,⋅⋅⋅,AN。(注意 A1∼AN

并不一定是按等差数
列中的顺序给出)
输出格式

输出一个整数表示答案。
数据范围

2≤N≤100000
,
0≤Ai≤109

输入样例：

5
2 6 4 10 20

输出样例：

10

样例解释

包含 2、6、4、10、20
的最短的等差数列是 2、4、6、8、10、12、14、16、18、20。

我太菜了，这都不会做，看到这题我一开始想的是二分，结果想法截然不同，答案其实很明显，是每个差值之间的最大公约数。

#include<iostream>
#include<algorithm>
using namespace std;
const   int N=1000010;
int a[N]; int gcd(int a,int b)
{
   
    return b?gcd(b,a%b):a;
}
int main()
{
   
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    cin>>a[i];
    sort(a,a+n);
    int d=0;
    bool flag=0;
    for(int i=0;i<n-1;i++)
    {
   
        if(a[i]==a[i+1])
        flag=1; else
        {
   
            flag=0;
            break;
        }
    }
    if(flag){
   
        printf("%d\n",n);
        return 0;
    }
    for(int i=1;i<n;i++)
    d=gcd(a[i]-a[i-1],d);
    int res=0;
    res=(a[n-1]-a[0])/d+1;
    cout<<res<<endl;
    return 0;
}