文章目录
前言
蓝桥杯2019省赛，编程题（C++）
一、题目描述
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一 部分的数列，只记得其中 N 个整数。
现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？
输入描述
输入的第一行包含一个整数 N。
第二行包含 N 个整数 A1,A2,⋅⋅⋅,AN。(注意 A1 ∼ AN 并不一定是按等差数列中的顺序给出)
其中，2≤N≤10的5次方，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。
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
二、思路
对于无序的数据要先从小到大排序。
从已有项中找到使得项数最小的公差，这个公差必然满足最大的公差，那么就是从每项数据之间的差值中找到一个最大公约数，题目的整体做法就出来了。那么在编程时，主要考虑以下几个方面，就可以了
- 最大公约数的函数构造
- 在多个差值中的求出最大公约数
- 注意公差为0的情况，直接输出n
- 项数 n = (an-a1)/d+1 ，d为公差
三、具体代码
#include<bits/stdc++.h>
using namespace std;
long gcd(long a,long b)
{
if(b==0)
{
return a;
}
return gcd(b,a%b);
}
int main()
{
long n;
cin>>n;
long item[100005]={0};
long dif[100005]={0}; //用来存储每一项之间的差值
for(long i=1;i<=n;i++)
{
cin>>item[i];
}
sort(item+1,item+n+1);
for(long i=2;i<=n;i++)
{
dif[i-1]=item[i]-item[i-1];
}
sort(dif+1,dif+n); //1~n-1排序
//找到一个差值序列中的最大公约数，是所有差值的因子，这个值就是最大的公差
for(long i=2;i<n;i++)
{
dif[1]=gcd(dif[i],dif[1]);
}
if(dif[1]>0) //考虑公差为0的特殊情况
{
long ans=(item[n]-item[1])/dif[1]+1;
cout<<ans<<endl;
}
else
{
cout<<n<<endl; //公差为0，即有n项
}
return 0;
}