OneCoder Avatar
OneCodercoderli.com · 1026 篇博文
五级

C++ 算法考级专栏

🎨 视觉封面

【GESP】C++五级真题(数论考点) luogu-P13014 [GESP202506 五级] 最大公因数

📅 2025-11-24·✍️ OneCoder·计算中...·⏱️ 8 分钟

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

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

题目要求

题目描述

对于两个正整数 ,他们的最大公因数记为 。对于 个正整数 ,他们的最大公因数为:

给定 个正整数 以及 组询问。对于第 组询问,请求出 的最大公因数,也即 。

输入格式

第一行,两个正整数 ,分别表示给定正整数的数量,以及询问组数。

第二行, 个正整数 。

输出格式

输出共 行,第 行包含一个正整数,表示 的最大公因数。

输入输出样例 #1

输入 #1
PLAINTEXT2 行
5 3
6 9 12 18 30
输出 #1
PLAINTEXT3 行
1
1
3

输入输出样例 #2

输入 #2
PLAINTEXT2 行
3 5
31 47 59
输出 #2
PLAINTEXT5 行
4
1
2
1
4

说明/提示

对于 的测试点,保证 ,。

对于所有测试点,保证 ,,。


题目分析

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

核心思想

题目要求计算数列 的最大公因数。 根据最大公因数的性质,多个数的 GCD 等于前两个数的 GCD 与第三个数的 GCD,即 。这意味着我们可以线性地遍历数组求出整体的 GCD。

优化思路

如果直接对于每一组询问 ,都遍历 个数计算 ,总时间复杂度为 。 考虑到 和 均可达到 ,总运算量达到 级别,这显然会超时。

观察数据范围,我们发现一个关键点: 的值非常小,保证 。 这是一个非常重要的提示。虽然 很大,但是数组中不同的数值最多只有 1000 个。 同时,最大公因数有一个性质:。也就是说,如果有多个相同的数,它们对最终 GCD 的贡献和一个数是一样的。 例如 。

算法流程

因此,我们不需要遍历 个数,只需要关心数值 到 中哪些数在数组 中出现过。

  1. 预处理:
  • 创建一个标记数组(桶),大小为 1005。
  • 读入 个数 。对于每个读入的数 ,将标记数组对应位置设为 1,表示该数值存在。这一步复杂度为 。
  1. 处理询问:
  • 对于每组询问 :
  • 初始化当前的最大公因数 cur_gcd 为 -1(或标记为未开始)。
  • 遍历数值范围 从 到 。
  • 如果标记数组显示数值 存在,则计算 cur_gcd = gcd(cur_gcd, j + i)。注意处理 cur_gcd 初始状态。
  • 这一步的复杂度为 。

复杂度分析

  • 时间复杂度:预处理 。查询总共 次,每次遍历 个数。总复杂度约为 。代入数据计算量大约在 级别。由于 GCD 运算很快,且大部分 可能不存在,实际运行效率很高。
  • 空间复杂度:只需要一个大小为 1005 的标记数组,空间复杂度为 。

示例代码

C++53 行
#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;
}

看完题解去实战!OneCoder C++ 信奥远征闯关平台 (oi.coderli.com)
💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!