题目描述

数学老师给小明出了一道等差数列求和的题目。
但是粗心的小明忘记了一部分的数列，只记得其中 N 个整数。
现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？

输入格式

输入的第一行包含一个整数 N。
第二行包含 N 个整数 A1,A2,⋅⋅⋅,AN。(注意 A1∼AN 并不一定是按等差数列中的顺序给出)

输出格式

输出一个整数表示答案。

输入样例

5
2 6 4 10 20

输出样例

10 

题解

求公差d的最大公约数(GCD)即可得到该等差数列的最大公差dmax，之后用每一个公差d/dmax+1即可得到结果。
注意
1. 首先需要将输入的每一项进行排序（使用<algorithm>库中的sort(begin,end+1,cmp)函数）
2. 求最大公约数可以直接调用_ _gcd(a,b)函数（<algorithm>库中）
3. 需要特判dmax为0的情况（否则对于一些测试用例会产生除数0的错误）（遇到除法时一定要考虑这一点）

代码

#include <iostream>
#include <string.h>
#include <algorithm>
#include <bits/stdc++.h>

using namespace std;

int main(){

    int n;
    scanf("%d",&n);
    long long int *a=new long long int[n+1];
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    sort(a,a+n);
    long long int *d=new long long int[n];
    for(int i=0;i<n-1;i++){
        d[i]=a[i+1]-a[i];
    }
    long long int dmin=d[0];
    for(int i=1;i<n-1;i++){
        dmin=__gcd(dmin,d[i]);
    }
    if(dmin==0){
        cout<<n<<endl;
        return 0;
    }
    int result=0;
    for(int i=0;i<n-1;i++){
        result+=d[i]/dmin;
    }
    result++;
    cout<<result<<endl;
    return 0;
}