以"最大真因数"为父结点建树,求两结点距离(编号可达 10⁹)。
有一棵以 1 为根、编号 1 ~ 10⁹ 的树。编号 k(k ≥ 2)的结点,父结点是 k 的因数中除 k 以外最大的那个。给定 q 组询问 (xᵢ, yᵢ),求两结点在树上的距离(边数)。
最大真因数最小质因子质因数分解LCA祖先链
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 q;随后 q 行每行 xᵢ、yᵢ |
| 输出 | 每组一个整数(距离) |
| 数据范围 | 1 ≤ q ≤ 1000 |
| 编号范围 | 1 ≤ xᵢ, yᵢ ≤ 10⁹ |
| 父结点规则 | k 的除自身外最大因数 |
k ≤ 10⁹ < 2³⁰,所以深度 ≤ 30以 120 = 2³ × 3 × 5 为例,我们一步步往上走(每次除以最小质因子)。
| 当前结点 | 分解 | 最小质因子 | 父结点 |
|---|---|---|---|
| 120 | 2³ × 3 × 5 | 2 | 120 / 2 = 60 |
| 60 | 2² × 3 × 5 | 2 | 60 / 2 = 30 |
| 30 | 2 × 3 × 5 | 2 | 30 / 2 = 15 |
| 15 | 3 × 5 | 3 | 15 / 3 = 5 |
| 5 | 5 | 5 | 5 / 5 = 1 |
| 1(根) | — | — | — |
往上走:120 → 60 → 30 → 15 → 5 → 1,共 5 步(深度 5)
1 → 5 → 15 → 30 → 60 → 120,也就是先乘大的质因子(5),再乘小的(3、2、2、2)——正好和"往上除最小质因子"相反。q = 3,询问 (1,3)、(2,5)、(4,8)。
x = 1:链 = [1],深度 0
y = 3:3 是质数 → 父结点 = 3/3 = 1
链 = [3, 1],深度 1
x 和 y 的共同祖先:1(深度 0)
距离 = 0 + 1 − 2×0 = 1
✅ 输出 1
x = 2:链 = [2, 1],深度 1
y = 5:链 = [5, 1],深度 1
共同祖先只有 1,深度 0
距离 = 1 + 1 − 0 = 2
✅ 输出 2
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] | 1 | 1 |
| 2 5 | [2, 1] | [5, 1] | 1 | 2 |
| 4 8 | [4, 2, 1] | [8, 4, 2, 1] | 4 | 1 |
输出 1、2、1 ✓
这组数据考验"LCA 不一定是 gcd"这个认识。
120 → 60 → 30 → 15 → 5 → 1
链(从 x 往上)= [120, 60, 30, 15, 5, 1],深度 5
深度 5
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
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 根本不在任何一条祖先链上!对每次询问分别构造两条祖先链(长度 ≤ 31),找最深公共结点
spf(k)(试除到 √k);② 不断 k /= spf(k) 得到整条链;③ 两链求最深公共结点,用 dep(x) + dep(y) − 2·dep(LCA) 得距离。预处理父结点数组并做倍增 LCA
| 方案 | 空间 | 可行性 |
|---|---|---|
| 祖先链 | O(1) | ✅ 可过 |
| 真建 10⁹ 结点树 | 约 8 GB | ❌ 不可行 |
第一行输入 q,随后 q 行输入 x 和 y,程序会构造祖先链并求距离。
点按钮开始 →
#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 = 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)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 | 1 2 1 | 题面样例 1 |
1 | 9 | 题面样例 2(LCA 不是 gcd) |
1 | 0 | 同一个结点,距离 0 |
1 | 2 | 两个不同质数,只能经根 |
1 | 4 | 4 的链 [4,2,1]、6 的链 [6,3,1],LCA = 1 → 2 + 2 = 4 |
1 | 1 | 8 的链 [8,4,2,1],16 的链 [16,8,4,2,1] → LCA = 8 |
spf:试除到 √k ≤ 31623每条链最多 31 个整数,加上一个哈希表。
✅ 约 3000 万次操作,可通过。若想更快,可以预先筛出 31623 以内的质数,用质数表去试除。
// 核心结论 // 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) | 所有求树上两点距离的问题 |