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

• 2020 年 2 月 26 日
• 笔记

题目

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