[蓝桥杯2019初赛]等差数列

题目描述

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

输入

输入的第一行包含一个整数N。
第二行包含N 个整数A1.A2,..., AN。(注意A1<=AN 并不一定是按等差数列中的顺序给出)
2<=N<=100000,0<=Ai<=10^9

输出

输出一个整数表示答案。

样例输入

5
2 6 4 10 20

样例输出

10

提示

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

题解

题目可以理解为：对于N个数，最少补多少个数可以使这些数成为等差数列，即项数要最小。

对于升序排列的N个数，首项(a1)和尾项(an)一定是固定的。因为没有必要在第一个数前或最后一个数后再补充数列元素。

项数 = (an-a1) / d + 1
公差d越大，项数越小

有如下两个结论（两者用一个即可）：

公差d一定可以整除数列中每一个数ai减第一个数a1，即：(ai-a1)%d = 0，则公差d最大为(ai-a1)的最大公因数
公差d一定可以整除数列中每一个数ai减最后一个数an，即：(an-ai)%d = 0，则公差d最大为(an-ai)的最大公因数
注意：需要特判公差全为0的情况

#include <iostream>
#include <algorithm>

using namespace std;
const int maxn = 100010;
int n,a[maxn];

//这是一个新的球最大公因数的函数~
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+1+n);
    for(int i=2;i<=n;i++)
        a[i]-=a[1];
    int d=a[2];
    for(int i=3;i<=n;i++)
        d=gcd(d,a[i]);
    //a[n]此时已经是a[n]-a[1]了
    if(d)
        cout<<a[n]/d+1<<endl;
    else
        cout<<n<<endl;
    return 0;
}