【GESP】C++五级真题（数论考点） luogu-P13014 [GESP202506 五级] 最大公因数
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
1
2
5 3
6 9 12 18 30
输出 #1
1
2
3
1
1
3
输入输出样例 #2
输入 #2
1
2
3 5
31 47 59
输出 #2
1
2
3
4
5
4
1
2
1
4
说明/提示
对于 $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))$。
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
