題目描述

數(shù)學(xué)老師給小明出了一道等差數(shù)列求和的題目。但是粗心的小明忘記了一部分的數(shù)列，只記得其中N 個整數(shù)。
現(xiàn)在給出這N 個整數(shù)，小明想知道包含這N 個整數(shù)的最短的等差數(shù)列有幾項？

輸入

輸入的第一行包含一個整數(shù)N。
第二行包含N 個整數(shù)A1.A2,..., AN。(注意A1<=AN 并不一定是按等差數(shù)列中的順序給出)
2<=N<=100000,0<=Ai<=10^9

輸出

輸出一個整數(shù)表示答案。

樣例輸入

5
2 6 4 10 20

樣例輸出

10

提示

包含2、6、4、10、20 的最短的等差數(shù)列是2、4、6、8、10、12、14、16、18、20。

題解

題目可以理解為：對于N個數(shù)，最少補(bǔ)多少個數(shù)可以使這些數(shù)成為等差數(shù)列，即項數(shù)要最小。

對于升序排列的N個數(shù)，首項(a1)和尾項(an)一定是固定的。因為沒有必要在第一個數(shù)前或最后一個數(shù)后再補(bǔ)充數(shù)列元素。

項數(shù) = (an-a1) / d + 1
公差d越大，項數(shù)越小

有如下兩個結(jié)論（兩者用一個即可）：

公差d一定可以整除數(shù)列中每一個數(shù)ai減第一個數(shù)a1，即：(ai-a1)%d = 0，則公差d最大為(ai-a1)的最大公因數(shù)
公差d一定可以整除數(shù)列中每一個數(shù)ai減最后一個數(shù)an，即：(an-ai)%d = 0，則公差d最大為(an-ai)的最大公因數(shù)
注意：需要特判公差全為0的情況

#include <iostream>
#include <algorithm>

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

//這是一個新的球最大公因數(shù)的函數(shù)~
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]此時已經(jīng)是a[n]-a[1]了
    if(d)
        cout<<a[n]/d+1<<endl;
    else
        cout<<n<<endl;
    return 0;
}