题目描述
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列，只记得其中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;
}
