蓝桥杯历届题目及解析汇总（附思路及代码）【点击此进入】
蓝桥杯，ACM算法学习【文档】【视频】大放送【点击此进入】
第八题
标题：等差数列 （时间限制: 1.0s 内存限制: 256.0MB 本题总分：20 分）###
【问题描述】 数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一 部分的数列，只记得其中 N 个整数。 现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有 几项？ 【输入格式】 输入的第一行包含一个整数 N。 第二行包含 N 个整数 A 1 ,A 2 ,··· ,A N 。(注意 A 1 ∼ 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 ≤ A i ≤ 10 9
解题思路：
先将给定的数字去重之后排序，公差应该是排序之后求出所有相邻数字之间差值的最大公约数。
代码：
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std
;
int value
[100010];
bool mark
[100010];
int gcd(int a
, int b
) {
int t
;
while (a
) {
t
= a
;
a
= b
% a
;
b
= t
;
}
return b
;
}
int main() {
int n
, d
, len
= 0, t
;
int maxx
= 0, minn
= 0x7fffffff;
cin
>> n
;
for (int i
= 0; i
< n
; i
++) {
scanf("%d", &t
);
if (!mark
[t
]) {
mark
[t
] = 1;
value
[len
++] = t
;
maxx
= max(maxx
, t
);
minn
= min(minn
, t
);
}
}
sort(value
, value
+ len
);
if (len
<= 1) {
cout
<< n
<< endl
;
} else {
d
= value
[1] - value
[0];
for (int i
= 2; i
< len
; i
++) {
d
= gcd(d
, value
[i
] - value
[i
-1]);
}
cout
<< ((maxx
- minn
) / d
+ 1) << endl
;
}
return 0;
}
蓝桥杯，ACM算法进阶资料大放送
