202506-最大公因数(luogu-P13014)

GESP C++ 2025年6月五级真题，数论考点，配合剪枝思想，题目难度⭐⭐★☆☆，五级来说难度相对简单。洛谷难度等级普及−

luogu-P13014 [GESP202506 五级] 最大公因数

题目要求

题目描述

对于两个正整数 $a,b$ ，他们的最大公因数记为 $\gcd(a,b)$ 。对于 $k > 3$ 个正整数 $c_1,c_2,\dots,c_k$ ，他们的最大公因数为：
$\gcd(c_1,c_2,\dots,c_k)=\gcd(\gcd(c_1,c_2,\dots,c_{k-1}),c_k)$
给定 $n$ 个正整数 $a_1,a_2,\dots,a_n$ 以及 $q$ 组询问。对于第 $i(1 \le i \le q)$ 组询问，请求出 $a_1+i,a_2+i,\dots,a_n+i$ 的最大公因数，也即 $\gcd(a_1+i,a_2+i,\dots,a_n+i)$ 。

输入格式

第一行，两个正整数 $n,q$ ，分别表示给定正整数的数量，以及询问组数。
第二行， $n$ 个正整数 $a_1,a_2,\dots,a_n$ 。

输出格式

输出共 $q$ 行，第 $i$ 行包含一个正整数，表示 $a_1+i,a_2+i,\dots,a_n+i$ 的最大公因数。

输入输出样例 #1

输入 #1

5 3
6 9 12 18 30

输出 #1

1
1
3

输入输出样例 #2

输入 #2

3 5
31 47 59

输出 #2

说明/提示

对于 $60\%$ 的测试点，保证 $1 \le n \le 10^3$ ， $1 \le q \le 10$ 。

对于所有测试点，保证 $1 \le n \le 10^5$ ， $1 \le q \le 10^5$ ， $1 \le a_i \le 1000$ 。

题目分析

这道题考察的是数论中的最大公因数（GCD）性质以及针对特定数据范围的优化策略。

核心思想

题目要求计算数列 $a_1+i, a_2+i, \dots, a_n+i$ 的最大公因数。根据最大公因数的性质，多个数的 GCD 等于前两个数的 GCD 与第三个数的 GCD，即 $\gcd(x, y, z) = \gcd(\gcd(x, y), z)$ 。这意味着我们可以线性地遍历数组求出整体的 GCD。

优化思路

如果直接对于每一组询问 $i$ ，都遍历 $n$ 个数计算 $\gcd(a_1+i, a_2+i, \dots, a_n+i)$ ，总时间复杂度为 $O(q \times n)$ 。考虑到 $n$ 和 $q$ 均可达到 $10^5$ ，总运算量达到 $10^{10}$ 级别，这显然会超时。

观察数据范围，我们发现一个关键点： $a_i$ 的值非常小，保证 $1 \le a_i \le 1000$ 。 这是一个非常重要的提示。虽然 $n$ 很大，但是数组中不同的数值最多只有 1000 个。同时，最大公因数有一个性质： $\gcd(x, x) = x$ 。也就是说，如果有多个相同的数，它们对最终 GCD 的贡献和一个数是一样的。例如 $\gcd(6, 6, 9) = \gcd(6, 9) = 3$ 。

算法流程

因此，我们不需要遍历 $n$ 个数，只需要关心数值 $1$ 到 $1000$ 中哪些数在数组 $a$ 中出现过。

预处理：

创建一个标记数组（桶），大小为 1005。
读入 $n$ 个数 $a_1, \dots, a_n$ 。对于每个读入的数 $x$ ，将标记数组对应位置设为 1，表示该数值存在。这一步复杂度为 $O(n)$ 。

处理询问：

对于每组询问 $i$ ：
初始化当前的最大公因数 cur_gcd 为 -1（或标记为未开始）。
遍历数值范围 $j$ 从 $1$ 到 $1000$ 。
如果标记数组显示数值 $j$ 存在，则计算 cur_gcd = gcd(cur_gcd, j + i)。注意处理 cur_gcd 初始状态。
这一步的复杂度为 $O(q \times \max(a_i))$ 。

复杂度分析

时间复杂度：预处理 $O(n)$ 。查询总共 $q$ 次，每次遍历 $1000$ 个数。总复杂度约为 $O(n + q \times 1000)$ 。代入数据计算量大约在 $10^8$ 级别。由于 GCD 运算很快，且大部分 $j$ 可能不存在，实际运行效率很高。
空间复杂度：只需要一个大小为 1005 的标记数组，空间复杂度为 $O(\max(a_i))$ 。

示例代码

#include <iostream>

// a数组用于标记数字是否存在。题目保证 1 <= ai <= 1000，
// 所以我们可以用一个大小为1005的数组来记录每个数字是否出现过。
int a[1005];

// 求最大公因数（Greatest Common Divisor）的函数
// 使用辗转相除法（欧几里得算法）
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int main() {
    int n, q;
    // 输入n（数字个数）和q（询问组数）
    std::cin >> n >> q;
    for (int i = 0; i < n; i++) {
        int num;
        std::cin >> num;
        // 标记数字num出现过。
        // 因为 gcd(x, x, y) = gcd(x, y)，重复的数字不影响最大公因数的结果，
        // 所以我们只需要记录哪些数字出现过，不需要记录出现的次数。
        a[num] = 1;
    }

    // 处理每一组询问
    // i 表示当前询问增加的数值，题目中询问是 a_j + i
    for (int i = 1; i <= q; i++) {
        int cur_gcd = -1;  // 用于存储当前计算出的最大公因数

        // 遍历所有可能的数值（1到1000）
        // 因为 ai 的范围很小，我们可以直接遍历数值范围
        for (int j = 1; j <= 1000; j++) {
            // 如果数值 j 在原数组中存在
            if (a[j] == 1) {
                if (cur_gcd == -1) {
                    // 如果是第一个遇到的数，直接作为当前的 GCD
                    cur_gcd = j + i;
                } else {
                    // 否则，计算当前 GCD 和 (j + i) 的最大公因数
                    // 更新 cur_gcd
                    cur_gcd = gcd(cur_gcd, j + i);
                }
            }
        }
        // 输出当前询问的答案
        std::cout << cur_gcd << std::endl;
    }
    return 0;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号

最后更新于 2025年11月26日

202506-奖品兑换(luogu-P13013)202509-数字选取(luogu-P14073)