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