C++ 算法考级专栏
🎨 视觉封面【GESP】C++五级真题(数论考点) luogu-P13014 [GESP202506 五级] 最大公因数
GESP C++ 2025年6月五级真题,数论考点,配合剪枝思想,题目难度⭐⭐★☆☆,五级来说难度相对简单。洛谷难度等级普及−
luogu-P13014 [GESP202506 五级] 最大公因数
题目要求
题目描述
对于两个正整数 ,他们的最大公因数记为 。对于 个正整数 ,他们的最大公因数为:
给定 个正整数 以及 组询问。对于第 组询问,请求出 的最大公因数,也即 。
输入格式
第一行,两个正整数 ,分别表示给定正整数的数量,以及询问组数。
第二行, 个正整数 。
输出格式
输出共 行,第 行包含一个正整数,表示 的最大公因数。
输入输出样例 #1
输入 #1
5 3
6 9 12 18 30输出 #1
1
1
3输入输出样例 #2
输入 #2
3 5
31 47 59输出 #2
4
1
2
1
4说明/提示
对于 的测试点,保证 ,。
对于所有测试点,保证 ,,。
题目分析
这道题考察的是数论中的最大公因数(GCD)性质以及针对特定数据范围的优化策略。
核心思想
题目要求计算数列 的最大公因数。 根据最大公因数的性质,多个数的 GCD 等于前两个数的 GCD 与第三个数的 GCD,即 。这意味着我们可以线性地遍历数组求出整体的 GCD。
优化思路
如果直接对于每一组询问 ,都遍历 个数计算 ,总时间复杂度为 。 考虑到 和 均可达到 ,总运算量达到 级别,这显然会超时。
观察数据范围,我们发现一个关键点: 的值非常小,保证 。 这是一个非常重要的提示。虽然 很大,但是数组中不同的数值最多只有 1000 个。 同时,最大公因数有一个性质:。也就是说,如果有多个相同的数,它们对最终 GCD 的贡献和一个数是一样的。 例如 。
算法流程
因此,我们不需要遍历 个数,只需要关心数值 到 中哪些数在数组 中出现过。
- 预处理:
- 创建一个标记数组(桶),大小为 1005。
- 读入 个数 。对于每个读入的数 ,将标记数组对应位置设为 1,表示该数值存在。这一步复杂度为 。
- 处理询问:
- 对于每组询问 :
- 初始化当前的最大公因数
cur_gcd为 -1(或标记为未开始)。 - 遍历数值范围 从 到 。
- 如果标记数组显示数值 存在,则计算
cur_gcd = gcd(cur_gcd, j + i)。注意处理cur_gcd初始状态。 - 这一步的复杂度为 。
复杂度分析
- 时间复杂度:预处理 。查询总共 次,每次遍历 个数。总复杂度约为 。代入数据计算量大约在 级别。由于 GCD 运算很快,且大部分 可能不存在,实际运行效率很高。
- 空间复杂度:只需要一个大小为 1005 的标记数组,空间复杂度为 。
示例代码
#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;
}所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI
欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。
猜你想读 · 相关文章推荐
【GESP】C++五级练习(初等数论考点) luogu-B3941 [GESP样题 五级] 小杨的锻炼
GESP C++ 五级初等数论考点练习,难度⭐⭐★☆☆。洛谷难度等级普及−
【GESP】C++五级(四级也可)练习(四级排序考点) luogu-B3951 [GESP样题 五级] 小杨的队列
GESP C++ 五级练习,但是核心的考点是四级排序内容,因为是GESP五级样例,所以归类在五级练习之中,其实四级同学完全可以练习,难度⭐⭐★☆☆。洛谷难度等级普及−
【GESP】C++五级真题(数论考点) luogu-B3871 [GESP202309 五级] 因数分解
GESP C++ 2023年9月五级真题,数论考点,难度⭐⭐★☆☆。洛谷难度等级普及−
OneCoder
一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

