題目描述
數(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ù)边翁，最少補多少個數(shù)可以使這些數(shù)成為等差數(shù)列，即項數(shù)要最小硕盹。
對于升序排列的N個數(shù)符匾，首項(a1)和尾項(an)一定是固定的。因為沒有必要在第一個數(shù)前或最后一個數(shù)后再補充數(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;
}
