题目
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列,只记得其中N 个整数。现在给出这N 个整数,小明想知道包含这N 个整数的最短的等差数列有几项?
思路
这个题目总体难度不大,考的是思路。
需要求出包含N个整数的最短等差数列,根据公式 (an - a1) / d + 1 = n,知道要想数列最短,则需要最大的公差d,于是问题转换为求出最大公差d。
公差d一定可以整除数列中每一个数ai减第一个数a1,即:(ai-a1)%d = 0,因此,公差d最大为(ai-a1)的最大公因数!于是,问题又转换到熟悉的gcd上了。
这里还需要特别注意d = 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]);
if(d)
cout<<a[n] / d + 1<<endl;
else
cout<<n<<endl;
return 0;
}