【問題描述】

數學老師給小明出了一道等差數列求和的題目。

但是粗心的小明忘記了一部分的數列，只記得其中 N 個整數。

現在給出這 N 個整數，小明想知道包含這 N 個整數的最短的等差數列有幾項？

【輸入格式】

輸入的第一行包含一個整數 N。

第二行包含 N 個整數 A₁, A₂, · · · , A_N。(注意 A₁ ～ A_N 并不一定是按等差數列中的順序給出)

【輸出格式】

輸出一個整數表示答案。

【樣例輸入】

5
2 6 4 10 20

【樣例輸出】

10

【樣例說明】

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

【評測用例規模與約定】

對于所有評測用例，2 ≤ N ≤ 100000，0 ≤ Ai ≤ 109。

Ideas

因為 A1 ～ AN 并不一定是按等差數列中的順序給出，所以要先排一下序。

然后既然這是又給等差數列，那么我們當然首先要求出第 i 項和第 i + 1 項的差，構成一個 diff 數組。

之后我們再求出 diff 數組中所有數的最大公約數，這個最大公約數就是包含這 N 個整數的最短的等差數列的公差。

然后就是等差數列的內容了，我們用最后一項減去第一項，然后用差除以上面算出來的公差，得到的結果就是這個最短的等差數列中一共有多少個公差，然后再加上1，就是等差數列的長度。

最后要考慮一下邊界情況，如果 diff 數組中所有數的最大公約數等于 0 呢，那就說明數組中存在相等的元素，此時我們直接返回 N 就可以了。

Code

Python

def gcd(a, b):return gcd(b, a % b) if b else aif __name__ == '__main__':n = int(input())nums = list(map(int, input().split(' ')))nums.sort()diff = [nums[i] - nums[i - 1] for i in range(1, n)]ans = gcd(diff[0], diff[1])for i in range(2, len(diff)):ans = gcd(ans, diff[i])print(((nums[-1] - nums[0]) // ans) + 1)

總結

以上是生活随笔為你收集整理的2019年第十届蓝桥杯 - 省赛 - C/C++大学B组 - H. 等差数列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。