P8682 [蓝桥杯 2019 省 B] 等差数列

[蓝桥杯 2019 省 B] 等差数列

题目描述

数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列，只记得其中 N 个整数。

现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？

输入格式

输入的第一行包含一个整数 N。

第二行包含 N 个整数 A_1,A_2,...,A_N。（注意 A_1 ∼ A_N 并不一定是按等差数列中的顺序给出 )。

输出格式

输出一个整数表示答案。

样例 #1

样例输入 #1

5
2 6 4 10 20

样例输出 #1

10

提示

包含 2,6,4,10,20 的最短的等差数列是 2,4,6,8,10,12,14,16,18,20。

对于所有评测用例，2 ≤ N ≤ 10^5，0 ≤ A_i ≤ 10^9。

蓝桥杯 2019 年省赛 B 组 H 题。

分析

一开始拿到这道题的时候，我的第一个想法是这样的：

1. 先给数组排序，计算两数之间最大的差值d
2. 从d开始判断是否满足为数列的公差，不满足就d--再继续判断，直到满足，如果d一直不满足到1，则结束，假设最小的公差为1.
3. 如果公差为0，即该等差数列的每一项都相同，则答案为数组长度。

但是，我还是太天真了，太傻了，看了网上大佬的题解后，深感羞愧不如。

这道题其实考的是欧几里得的求最大公约数，涉及到一点点数论的知识。

我们只需要求出每一项与第一项的差值，然后这些差值求一个最大公约数，该最大公约数就是等差数列的公差。

对于无序的数据要先从小到大排序。

从已有项中找到使得项数最小的公差，这个公差必然满足最大的公差，那么就是从每项数据之间的差值中找到一个最大公约数，题目的整体做法就出来了。那么在编程时，主要考虑以下几个方面，就可以了

• 最大公约数的函数构造
• 在多个差值中的求出最大公约数
• 注意公差为0的情况，直接输出n
• 项数 n = (an-a1)/d+1 ，d为公差

提交答案

#include<bits/stdc++.h>
using namespace std;

//递归算法求解的gcd函数，可以运行成功，最后可以得100分
long gcd(long a,long b)
{
    if(b==0)
    {
        return a;
    }
    return gcd(b,a%b);
}

/*
循环算法的gcd函数，也可以运行成功，但是最后只得了90分
long gcd(long a,long b)
{
    while(b^=a^=b^=a%=b);
    return a;
}
*/

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;
}