专栏首页卡尼慕1466: [蓝桥杯2019初赛]等差数列

1466: [蓝桥杯2019初赛]等差数列

题目

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

本文分享自微信公众号 - 卡尼慕(gh_40138f7dc7d3),作者:卡尼幕

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 1022 D进制的A+B (20 分)

    输入两个非负 10 进制整数 A 和 B (≤230−1),输出 A+B 的 D (1<D≤10)进制数。

    可爱见见
  • 1087 有多少不同的值 (20 分)

    当自然数 n 依次取 1、2、3、……、N 时,算式 ⌊n/2⌋+⌊n/3⌋+⌊n/5⌋ 有多少个不同的值?(注:⌊x⌋ 为取整函数,表示不超过 x 的最大自然...

    可爱见见
  • 1073 多选题常见计分法 (20 分)

    可爱见见
  • 洛谷P4424 [HNOI/AHOI2018]寻宝游戏(思维题)

    那么我们把每一列上的数和他之前的操作符分别拿出来看成一些序列,显然这个序列要满足最后一个\(\mid 1\)要在\(\& 0\)之后

    attack
  • Hackerrank GCD Product(莫比乌斯反演)

    attack
  • 海量数据处理之bitmap

    本文将讲述Bit-Map算法的相关原理,Bit-Map算法的一些利用场景,例如BitMap解决海量数据寻找重复、判断个别元素是否在海量数据当中等问题.最后说说B...

    Spark学习技巧
  • BZOJ3262: 陌上花开(cdq分治)

    第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。

    attack
  • 2018 团队设计天梯赛题解---华山论剑组

    2018 年度的团队设计天梯赛前几天结束了。但是成绩真的是惨不忍睹。。。毕竟是团队的比赛,如果团队平均水平不高的话,单凭一个人,分再高也很难拉起来(当然,一个人...

    指点
  • HDU 2196 Computer(树的直径)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2196

    Ch_Zaqdt
  • 【CodeForces 730H】Car Repair Shop

    模拟,先看从s[i]时刻开始修理,和之前i-1个是否冲突。如果冲突,就枚举每个s[j]+d[j]时刻开始,看是否冲突,再从中选择最小的时刻。

    饶文津

扫码关注云+社区

领取腾讯云代金券