1246. 等差数列
摘要
Title: 1246. 等差数列
Tag: gcd
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
1246. 等差数列
-
题意
数学老师给小明出了一道等差数列求和的题目。
但是粗心的小明忘记了一部分的数列，只记得其中 N 个整数。
现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？ -
思路
排完序后，求从小到大找相邻两数差的gcd，即是等差数列的公差
当公差为0时，答案就为n -
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23'''
Author: NEFU AB-IN
Date: 2022-03-31 19:49:38
FilePath: \ACM\Acwing\1246.py
LastEditTime: 2022-03-31 19:49:38
'''
def gcd(a, b):
return gcd(b, a % b) if b else a
n = int(input())
a = list(map(int, input().split()))
a.sort()
d = a[1] - a[0]
for i in range(1, n):
d = gcd(d, a[i] - a[i - 1])
if d:
print((a[-1] - a[0]) // d + 1)
else:
print(n)