GESP 2025年6月 最大因数 题解|基础数学详细讲解
记录一道 GESP 2025年6月 的基础数学真题。这类题在考试里属于必得分项,核心就那几行代码,关键是别在小细节上丢分。
题目来源:ACGO A61989 | 2025年6月 六级
赛事场次:2025年6月 六级
一、题目信息
题目名称:最大因数
赛事场次:2025年6月 六级
难度定位:六级
涉及知识点:数学 最近公共祖先
题目链接:https://www.acgo.cn/problemset/info/61989
先说坑点(不提前知道必错)
- 倍增预处理;深度对齐与同时上跳。
- 数据量较大,朴素做法可能超时,需估算复杂度。
题意简述
给定一棵有 10⁹ 个结点的有根树,这些结点依次以 1, 2, …, 10⁹ 编号,根结点的编号为 1。对于编号为 k(2 ≤ k ≤ 10⁹)的结点,其父结点的编号为 k 的因数中除 k 以外最大的因数。
现在有 q 组询问,第 i(1 ≤ i ≤ q)组询问给定 xᵢ, yᵢ,请你求出编号分别为 xᵢ, yᵢ 的两个结点在这棵树上的距离。两个结点之间的距离是连接这两个结点的简单路径所包含的边数。
前置知识
下面先把需要的基础知识理一遍,不熟悉的朋友可以跟着看,熟悉的直接跳过。
整数除法与取余:C++ 中两个整数相除结果仍是整数,小数部分直接舍去,例如 5/2 得到 2 而不是 2.5。要得到小数必须先把其中一个数转成 double。
取余运算:a % b 得到 a 除以 b 的余数,常用来判断整除关系,例如 n % 2 == 0 表示 n 是偶数。
二、思路分析
先看清楚题目要我们做什么
把题目读两遍,我们提取出关键信息:输入是什么、要输出什么、有哪些约束条件。这道题考查的是基础数学,属于这类题里比较基础的一道,把题目要求一步步翻译成代码逻辑就能解决。
我的思考过程
读完题之后,我的第一反应是这样的:我们可以先分别处理出节点 x 和 y 到节点 1 这条链上的数字,由于 q 数据范围小,10⁹ 以内的数到根节点 1 的链长实际上不多,所以我们可以暴力求解两个数在树上到最近公共祖先的距离,两距离求和即是答案。
需要说明的是,上面这个思路是把题目要求直译成代码得到的,没有用到什么高级技巧。对于这类基础题,读准题意加写对边界比追求巧妙解法更重要,因为考试里这种题是必须拿满分的。
三、完整代码 + 逐行注释
// 最大因数树:父结点是 k 的最大真因数。求 x,y 距离 = 两条到根链的 LCA 深度
#include <cstdio>
#include <vector>
using namespace std;
int maxProperFactor(int k) {
for (int i = 2; (long long)i * i <= k; i++) // 遍历
if (k % i == 0) return k / i; // 最小因子 i 对应最大真因数 k/i
return 1; // 质数 -> 父结点 1
}
int main() {
int q; scanf("%d", &q);
while (q--) {
int x, y; scanf("%d%d", &x, &y);
vector<int> px, py;
int t = x;
while (t != 1) { px.push_back(t); t = maxProperFactor(t); }
px.push_back(1); // px: x -> ... -> 1
t = y;
while (t != 1) { py.push_back(t); t = maxProperFactor(t); }
py.push_back(1); // py: y -> ... -> 1
// 两条链均为从自身到根,公共后缀即为公共祖先链;找最后一个相同的
int i = px.size() - 1, j = py.size() - 1, common = 0;
while (i >= 0 && j >= 0 && px[i] == py[j]) { common++; i--; j--; }
int dx = (int)px.size() - 1, dy = (int)py.size() - 1;
printf("%d\n", dx + dy - 2 * (common - 1));
}
return 0;
}
四、代码分段拆解
为了看得更清楚,我们把代码按功能分成几段解释。
第一步:引入头文件
#include <cstdio>
#include <vector>
using namespace std;
#include <iostream> 提供输入输出功能,using namespace std; 让我们能直接写 cin、cout 而不用加前缀。这两行是几乎所有 C++ 程序的开头,照写即可。
第二步:读入数据
int q; scanf("%d", &q);
int x, y; scanf("%d%d", &x, &y);
注意变量的类型要能装下题目的数据。本题数据范围到 10⁹,如果接近或超过 21 亿,就必须用 long long 而不是 int。
第三步:核心处理逻辑
for (int i = 2; (long long)i * i <= k; i++)
while (q--) {
while (t != 1) { px.push_back(t); t = maxProperFactor(t); }
while (t != 1) { py.push_back(t); t = maxProperFactor(t); }
这一段是整道题的关键,也是基础数学的体现。看循环的三个要素:从哪里开始、什么时候结束、每次怎么变化。这三个要素任何一个写错,结果都会不对。
第四步:按要求输出
printf("%d\n", dx + dy - 2 * (common - 1));
输出格式必须和题目要求的完全一致。很多同学算法完全正确却因为少了一个换行或者空格多寡不对而 WA,这种分丢得最可惜。
五、实例模拟
把样例代进去手动模拟一遍,思路会更清晰。
以题目的第一组样例为例:
样例输入
3
1 3
2 5
4 8
样例输出
1
2
1
把这份输入代进代码,程序会先把数据依次读入,然后进入循环逐个判断,把满足条件的值累积起来,最后按格式输出。建议你对照着代码在纸上走一遍前两次循环,确认自己对每一步的理解都和程序一致。
题目另外还给了 1 组样例,做完之后建议把剩下的样例都跑一遍,全部通过再提交,能避开大部分边界问题。
六、踩坑总结
下面是做这道题时最容易出错的地方,对照自己的代码检查一下:
- 变量类型不够用:题目数据范围较大,累加结果可能突破 21 亿,必须用
long long声明累加变量,用int会溢出得到负数或错误值。 - 区间边界取错:题目说「L 到 R 之间包括两端」,循环就要写
for (int i = L; i <= R; i++)。写成i < R会漏掉最后一个数,这是最常见的失分点。 - 输出格式不符:题目要求输出几行就输出几行,行末换行、数字之间的空格都要严格对齐,算法对了但格式错了同样判 WA,这种分丢得最冤。
- 特殊情况没特判:把最小数据、最大数据、答案恰好等于 0 的情况各测一遍。特别是边界输入,出题人最喜欢在这里设陷阱。
七、知识点拓展
最后总结一下这道题带给我们的通用经验:
- 本题考查基础数学的基本写法,这类题在考试中属于必得分项,要练到能默写。
- 写完代码后建议自己造几组边界数据测试,特别是最小值和最大值。
- 同一知识点在不同场次反复出现,把这道题的写法吃透,后面遇到同类题可以直接套用。
八、适用人群
刚学完基础数学、正在准备 六级 考试的同学,适合用这道题检验掌握程度。
这道题就讲到这里。我会持续更新各场次真题的详细拆解,需要系统复习的同学可以关注这个系列。有问题欢迎评论区讨论。
更多推荐



所有评论(0)