2019年第十届蓝桥杯省赛-H.等差数列

2022-03-23 · 109次阅读 · 原创 · 数据结构与算法

#蓝桥杯 #题解 #数学

原题链接

题面

数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列，只记得其中 N 个整数。

现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？

输入描述

输入的第一行包含一个整数 N。

第二行包含 N 个整数 $A_1,A_2,··· ,A_N$ 。(注意 $A_1 - A_N$ 并不一定是按等差数列中的顺序给出)

其中， $2 \leq N \leq 10^5，0 \leq A_i \leq 10^9$ 。

输出描述

输出一个整数表示答案。

输入输出样例

5
2 6 4 10 20

输出样例

样例说明：包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、 18、20。

题解

数学，最大公因数

要求该等差数列的长度最短，则即对应的公差最大。

由题，将数组 a 读入后先进行排序，我们不妨设最大公差为 d，则 a 数组每相邻两项的差值为 $k_1\times d,k_2\times d,k_3\times d,\cdots,k_{n-1}\times d$ ，其中 $k_i \ge 1$ ，则推出下式子：

$d = \gcd_{i = 1}^{n- 1}(k_i\times d)$

最后，最大公差计算出来了，则最短等差数列长度为

$len = \frac{a_n - a_1}{d}+ 1$

具体见代码。

代码

#include<bits/stdc++.h>

using namespace std;

#define gcd(a, b) __gcd(a, b)
const int N = 1e5 + 5;
int n, a[N];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    sort(a, a + n);
    if (a[0] == a[n - 1]) {
        cout << n << endl;
        exit(0);
    }

    int d = a[1] - a[0];
    for (int i = 1; i < n - 1; ++i) {
        int s = abs(a[i + 1] - a[i]);
        d = gcd(d, s);
    }
    cout << (a[n - 1] - a[0]) / d + 1 << endl;

    return 0;
}

标题：	2019年第十届蓝桥杯省赛-H.等差数列
链接：	https://www.fightingok.cn/detail/218
更新：	2022-09-18 22:49:13
版权：	本文采用 CC BY-NC-SA 3.0 CN 协议进行许可