记录一道 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 组样例,做完之后建议把剩下的样例都跑一遍,全部通过再提交,能避开大部分边界问题。

六、踩坑总结

下面是做这道题时最容易出错的地方,对照自己的代码检查一下:

  1. 变量类型不够用:题目数据范围较大,累加结果可能突破 21 亿,必须用 long long 声明累加变量,用 int 会溢出得到负数或错误值。
  2. 区间边界取错:题目说「L 到 R 之间包括两端」,循环就要写 for (int i = L; i <= R; i++)。写成 i < R 会漏掉最后一个数,这是最常见的失分点。
  3. 输出格式不符:题目要求输出几行就输出几行,行末换行、数字之间的空格都要严格对齐,算法对了但格式错了同样判 WA,这种分丢得最冤。
  4. 特殊情况没特判:把最小数据、最大数据、答案恰好等于 0 的情况各测一遍。特别是边界输入,出题人最喜欢在这里设陷阱。

七、知识点拓展

最后总结一下这道题带给我们的通用经验:

  • 本题考查基础数学的基本写法,这类题在考试中属于必得分项,要练到能默写。
  • 写完代码后建议自己造几组边界数据测试,特别是最小值和最大值。
  • 同一知识点在不同场次反复出现,把这道题的写法吃透,后面遇到同类题可以直接套用。

八、适用人群

刚学完基础数学、正在准备 六级 考试的同学,适合用这道题检验掌握程度。

这道题就讲到这里。我会持续更新各场次真题的详细拆解,需要系统复习的同学可以关注这个系列。有问题欢迎评论区讨论。

Logo

智能硬件社区聚焦AI智能硬件技术生态,汇聚嵌入式AI、物联网硬件开发者,打造交流分享平台,同步全国赛事资讯、开展 OPC 核心人才招募,助力技术落地与开发者成长。

更多推荐