GESP 题解库 / 6 级题解 / [GESP202506 六级] 最大因数 · 第 7 / 27 题
GESP202506 六级 · P13016 · 中等

最大因数

以"最大真因数"为父结点建树,求两结点距离(编号可达 10⁹)。

📊
q ≤ 1000, x ≤ 10⁹
数据范围
🔢
int
数值类型
⚡
O(√x) / 次询问
时间复杂度
🎯
最大真因数 = x/最小质因子
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

有一棵以 1 为根、编号 1 ~ 10⁹ 的树。编号 k(k ≥ 2)的结点,父结点是 k 的因数中除 k 以外最大的那个。给定 q 组询问 (xᵢ, yᵢ),求两结点在树上的距离(边数)。

💡
人话翻译:两个关键观察——
① k 的最大真因数 = k ÷ k 的最小质因子。所以"往上走一步"就是除掉一个最小的质因子。
② 因此深度 = k 的质因子总个数(含重数),不超过 30 层(因为 2³⁰ > 10⁹)。
于是把两条祖先链都列出来找 LCA,距离 = 深度和 − 2 × LCA 深度。

🔍 关键词提取

最大真因数最小质因子质因数分解LCA祖先链

已知条件

项目说明
输入第一行 q;随后 q 行每行 xᵢ、yᵢ
输出每组一个整数(距离)
数据范围1 ≤ q ≤ 1000
编号范围1 ≤ xᵢ, yᵢ ≤ 10⁹
父结点规则k 的除自身外最大因数

需要解决的问题

02
思维导图
整理解题思路的全貌
🌲 往上走 = 除掉最小质因子
🔑 核心转化
k 的最大真因数 = k / spf(k)
spf 表示"最小质因子"
所以父结点 = k 除一个最小质因子
问题变成质因数分解
📏 深度
深度 = Ω(k)(质因子总个数含重数)
k ≤ 10⁹ < 2³⁰
所以深度 ≤ 30
祖先链很短
📐 距离
距离 = dep(x) + dep(y) − 2 × dep(LCA)
祖先链列出来找 LCA
各链长度 ≤ 31
O(31) 判断
⚠️ 易错点
把"最大真因数"当成 k/最大质因子
以为深度是"不同质因子个数"
用递归或按编号建树(10⁹ 个结点不可能)
漏掉 x 或 y 为 1 的情形
03
样例手算推导
样例的完整推演

🧮 先把"祖先链"看明白

以 120 = 2³ × 3 × 5 为例,我们一步步往上走(每次除以最小质因子)。

当前结点分解最小质因子父结点
1202³ × 3 × 52120 / 2 = 60
602² × 3 × 5260 / 2 = 30
302 × 3 × 5230 / 2 = 15
153 × 5315 / 3 = 5
5555 / 5 = 1
1(根)———

往上走:120 → 60 → 30 → 15 → 5 → 1,共 5 步(深度 5)

🔑
注意链的形状:从根往下看是 1 → 5 → 15 → 30 → 60 → 120,也就是先乘大的质因子(5),再乘小的(3、2、2、2)——正好和"往上除最小质因子"相反。
另外验证一下 深度 = Ω(120) = 3 + 1 + 1 = 5 ✓,即"质因子总个数(含重数)"。

🧮 样例 1:三组询问

q = 3,询问 (1,3)、(2,5)、(4,8)。

1
(1, 3)

x = 1:链 = [1],深度 0

y = 3:3 是质数 → 父结点 = 3/3 = 1

链 = [3, 1],深度 1

x 和 y 的共同祖先:1(深度 0)

距离 = 0 + 1 − 2×0 = 1

✅ 输出 1

2
(2, 5)

x = 2:链 = [2, 1],深度 1

y = 5:链 = [5, 1],深度 1

共同祖先只有 1,深度 0

距离 = 1 + 1 − 0 = 2

✅ 输出 2

3
(4, 8)

x = 4 = 2²:链 = [4, 2, 1],深度 2

y = 8 = 2³:链 = [8, 4, 2, 1],深度 3

从 y 往上找:8 不在 x 链中;4 在 x 链中 → LCA = 4

LCA 深度 = 2

距离 = 2 + 3 − 2×2 = 1

✅ 输出 1

📊 汇总

询问x 的链y 的链LCA距离
1 3[1][3, 1]11
2 5[2, 1][5, 1]12
4 8[4, 2, 1][8, 4, 2, 1]41

输出 1、2、1 ✓

🧮 样例 2:(120, 650),答案 9

这组数据考验"LCA 不一定是 gcd"这个认识。

1
x = 120 的祖先链

120 → 60 → 30 → 15 → 5 → 1

链(从 x 往上)= [120, 60, 30, 15, 5, 1],深度 5

深度 5

2
y = 650 的祖先链

650 = 2 × 5² × 13,最小质因子是 2

650 → 325(除以 2)

325 = 5² × 13,最小质因子 5

325 → 65 → 13(各除以 5)

13 是质数 → 13 → 1

链 = [650, 325, 65, 13, 1],深度 4

深度 4

3
找 LCA

x 的祖先集合 = {120, 60, 30, 15, 5, 1}

y 的祖先集合 = {650, 325, 65, 13, 1}

交集只有 {1} → LCA = 1,深度 0

距离 = 5 + 4 − 0 = 9

✅ 输出 9

答案 9 ✓

⚠️
这一组特别值得注意:gcd(120, 650) = 10,但 LCA 并不是 10——因为 10 根本不在任何一条祖先链上!
原因是"往上走"必须每次都除以最小质因子,而 120 和 650 的小质因子剥离顺序不同。所以本题的 LCA 不能简单用 gcd 来算。
04
解法对比
祖先链求 LCA vs 按编号建树

⚔️ 解法对比

🟢 逐次除以最小质因子 + 链上求 LCA(推荐) 推荐

对每次询问分别构造两条祖先链(长度 ≤ 31),找最深公共结点

  • 每组询问 O(√x + Ω(x))
  • q = 1000 时约 3 × 10⁷
  • 代码 40 行
  • 空间 O(1)
💡
三个步骤:① 求 spf(k)(试除到 √k);② 不断 k /= spf(k) 得到整条链;③ 两链求最深公共结点,用 dep(x) + dep(y) − 2·dep(LCA) 得距离。

🟠 按编号真的建一棵 10⁹ 结点的树

预处理父结点数组并做倍增 LCA

  • 需要 10⁹ 大小的数组
  • 内存 完全不可行
  • 时间也不可能
  • 忽略了"链很短"这个关键事实
⚠️
量级对比:10⁹ 个结点 vs 每条链 ≤ 31 个结点——差了 3000 万倍。所以本题根本不需要建树,只要"按需构造两条链"即可。

📈 性能对比

方案空间可行性
祖先链O(1)✅ 可过
真建 10⁹ 结点树约 8 GB❌ 不可行
05
算法流程图
构造祖先链并求 LCA
开始读入 q处理每组询问 x、y对 x:不断求最小质因子并相除,记录整条祖先链与各点深度对 y:同样构造祖先链(从 y 往上)从 y 往上逐个检查是否在 x 的祖先集合中该结点是否在 x 的祖先链中?是 ✓它就是 LCA,停止查找否 ✗继续往上输出 dep(x) + dep(y) − 2 × dep(LCA)处理下一组询问
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🌲 树上距离计算器

第一行输入 q,随后 q 行输入 x 和 y,程序会构造祖先链并求距离。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

// 求 k 的最小质因子(k >= 2)
int spf(int k) {
    for (int i = 2; (long long)i * i <= k; i++)
        if (k % i == 0) return i;
    return k;                     // k 本身是质数
}

// 求 x 到根的整条祖先链(不含根之后),返回 {链结点}
vector<int> chainOf(int x) {
    vector<int> c;
    c.push_back(x);
    while (x > 1) {
        x /= spf(x);              // 往上走一步:除以最小质因子
        c.push_back(x);
    }
    return c;
}

int main() {
    int q;
    scanf("%d", &q);

    while (q--) {
        int x, y;
        scanf("%d %d", &x, &y);

        vector<int> cx = chainOf(x);
        vector<int> cy = chainOf(y);

        int depX = (int)cx.size() - 1;
        int depY = (int)cy.size() - 1;

        // 把 x 的祖先放进集合(记录深度)
        unordered_map<int, int> depOfX;
        for (int i = 0; i < (int)cx.size(); i++)
            depOfX[cx[i]] = depX - i;

        // 从 y 往上找第一个属于 x 祖先的结点 —— 即 LCA
        int depLca = 0;
        for (int j = 0; j < (int)cy.size(); j++) {
            auto it = depOfX.find(cy[j]);
            if (it != depOfX.end()) { depLca = it->second; break; }
        }

        printf("%d\n", depX + depY - 2 * depLca);
    }
    return 0;
}
🔑
为什么"最大真因数 = k / 最小质因子"?设 k = d × m(d 是某个真因数)。要让因数 m 最大,就要让另一个因子 d 最小。而 d 最小只能取 k 的最小质因子(若取合数,它还能再分解出更小的质因子,对应更大的 m)。所以每往上走一步 = 除掉一个最小质因子,这使得"深度 = 质因子总个数"这个结论非常直观。

📖 关键几行怎么看

代码作用为什么这样写
spf(k)最小质因子试除到 √k 即可,第一个整除的就是最小质因子
x /= spf(x)往上走一步父结点 = 除以最小质因子
while (x > 1)链长度深度 = Ω(x) ≤ 30
depX + depY - 2 * depLca距离公式树上距离的标准公式
⚠️
四个坑:① 把"最大真因数"错当成 k / 最大质因子;② 以为深度是"不同质因子个数"(应是含重数的个数);③ 试图真的建一棵 10⁹ 结点的树(会爆内存);④ 忘记处理 x = 1 的情形(此时链只有 [1],深度 0)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
3
1 3 / 2 5 / 4 8
1
2
1
题面样例 1
1
120 650
9题面样例 2(LCA 不是 gcd)
1
1 1
0同一个结点,距离 0
1
2 3
2两个不同质数,只能经根
1
4 6
44 的链 [4,2,1]、6 的链 [6,3,1],LCA = 1 → 2 + 2 = 4
1
8 16
18 的链 [8,4,2,1],16 的链 [16,8,4,2,1] → LCA = 8
✅
自查清单:① 除以最小质因子吗?② 深度含重数吗?③ 用链求 LCA 吗?

🚨 易错点清单

⚠️
父结点算错:最大真因数 = k ÷ 最小质因子,不是除以最大质因子。
⚠️
深度定义错:深度 = 质因子总个数(含重数),如 12 = 2²×3 的深度是 3。
⚠️
试图建整棵树:10⁹ 个结点不可能,应按需构造"长度 ≤ 31"的祖先链。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

单组询问
O(√x + Ω(x))
空间复杂度
O(Ω(x)) ≤ 31
q 最大
1000
总运算量
约 3 × 10⁷

时间怎么算的?

空间都用在哪?

每条链最多 31 个整数,加上一个哈希表。

✅ 约 3000 万次操作,可通过。若想更快,可以预先筛出 31623 以内的质数,用质数表去试除。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 核心结论
// 1. k 的最大真因数 = k / spf(k)   (spf = smallest prime factor)
// 2. 深度 = Ω(k)(质因子个数,含重数)≤ 30(因 2^30 > 10^9)
// 3. 距离 = dep(x) + dep(y) - 2 * dep(LCA)

// 求最小质因子的加速版(预筛质数表)
int primes[MAXP], pc;
// 先用埃氏筛打出 sqrt(10^9) = 31623 以内的质数
int spfFast(int k) {
    for (int i = 0; i < pc && (long long)primes[i]*primes[i] <= k; i++)
        if (k % primes[i] == 0) return primes[i];
    return k;
}

// 树上距离公式的通用形式
// dist(u, v) = dep(u) + dep(v) - 2 * dep(lca(u, v))
// 本题的树很浅(≤ 30 层),所以直接暴力枚举链求 LCA 就够

// "编号即结点"的隐式树
// 类似问题:以 n/最小质因子 为父结点的树、约数树、整除格等

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
最大真因数= k / 最小质因子所有"因数关系建树"的题
隐式树按需构造链而非真建树编号范围极大但深度很小的树
树上距离dep 和 − 2×dep(LCA)所有求树上两点距离的问题
🌟
思考题:如果题目改成"求 x 的第 k 级祖先"(往上走 k 步),该怎么做?(提示:直接走 k 步就行——每次除以最小质因子,走 k 步最多 30 次运算。本题的树"又宽又浅"(10⁹ 个结点但只有 30 层),这种结构下很多在图上看很麻烦的问题都会变得简单。)