10719.最⼤因数

markdown
复制
1# 最⼤因数 题解
2
3## 题目大意
4
5有一棵含有 $10^9$ 个结点的有根树，根结点编号为 $1$。对于编号为 $k$（$2 \le k \le 10^9$）的结点，它的父结点是「$k$ 的因数中除了 $k$ 以外最大的那一个」。  
6现在有 $q$ 组询问，每组询问给出两个结点的编号 $x_i, y_i$，求这两个结点在树上的距离（即连接两点的简单路径所包含的边数）。
7
8---
9
10## 题目分析
11
12### 1. 树的结构
13
14我们需要先弄清楚这棵树的形态。以 $k=6$ 为例：
15
16- $6$ 的因数有：$1,2,3,6$；
17- 除 $6$ 以外最大的是 $3$，所以 $6$ 的父亲是 $3$。
18
19再比如 $k=12$：
20
21- $12$ 的因数：$1,2,3,4,6,12$；
22- 最大真因数是 $6$，所以 $12$ 的父亲是 $6$。
23
24仔细观察可以发现，**一个结点的最大真因数恰好等于该结点除以它的最小质因子**。  
25证明很简单：设 $k$ 的最小质因子为 $p$，则 $k/p$ 是 $k$ 的真因数。任何大于 $k/p$ 的真因数 $d$ 必然满足 $k = d \times m$ 且 $m < p$，但由于 $p$ 是最小质因子，$m$ 不可能存在（除非 $m=1$，即 $d=k$）。因此 $k/p$ 就是最大真因数。
26
27于是我们得到了一个非常重要的性质：
28
29> **结点 $x$ 的父结点为 $x / p$，其中 $p$ 是 $x$ 的最小质因子。**
30
31### 2. 从结点到根的路径
32
33根据上述性质，从任意结点 $x$ 向上走到根 $1$ 的路径就是不断进行「除以当前数的最小质因子」的过程。
34
35以 $x=12$（质因数 $2^2 \times 3$）为例：
36
37- $12$ 的最小质因子是 $2$ → 父结点 $12/2 = 6$；
38- $6$ 的最小质因子是 $2$ → 父结点 $6/2 = 3$；
39- $3$ 的最小质因子是 $3$ → 父结点 $3/3 = 1$；
40- 到根为止，路径为：$12 \to 6 \to 3 \to 1$。
41
42可以看出，路径上的数正好是原数按质因子从小到大的顺序，**每次除去一个最小质因子**得到的各个中间结果。
43
44### 3. 两个结点的距离与最近公共祖先（LCA）
45
46树上的距离 = $x$ 到 LCA 的距离 + $y$ 到 LCA 的距离。  
47由于我们已经可以求出任意结点到根的路径序列，那么两个结点的 LCA 就是它们路径序列中**第一个相同的结点**（即从下往上第一次相遇的点）。
48
49---
50
51## 解题思路
52
53对于每组询问 $(x, y)$：
54
551. **分解质因数**：对 $x$ 和 $y$ 分别进行质因数分解，并记录下每次除以最小质因子后得到的中间值，生成从自身到根 $1$ 的路径序列 $a$ 和 $b$。  
56   - $a[0] = x$，$a[1] = x / p_1$，$a[2] = a[1] / p_2$，… 直到 $1$。
57   - 序列自然是从大到小排列的（从 $x$ 到 $1$）。
58
592. **双指针求 LCA**：  
60   用两个指针 $px, py$ 分别扫描 $a$ 和 $b$ 的当前元素：
61   - 如果 $a[px] > b[py]$，说明 $a$ 当前结点更深，令 $px$ 前进；
62   - 如果 $a[px] < b[py]$，则令 $py$ 前进；
63   - 直到 $a[px] = b[py]$，此时该结点即为 LCA。
64
653. **计算距离**：  
66   指针移动的步数就是各自走到 LCA 的边数，因此答案 = $px + py$。
67
68---
69
70## 算法说明
71
72参考代码中 `factorize` 函数的具体实现：
73
74```cpp
75void factorize(int x, int a[], int &cnt) {
76    a[0] = x;
77    t = 0;
78    // 分解质因数，依次存入 f[1..t]
79    for (int i = 2; i * i <= x; i++) {
80        while (x % i == 0) {
81            f[++t] = i;
82            x /= i;
83        }
84    }
85    if (x > 1) f[++t] = x;
86    // 生成路径序列 a
87    for (int i = 1; i <= t; i++)
88        a[i] = a[i - 1] / f[i];
89    cnt = t;
90}

• f 数组按从小到大的顺序存储了 $x$ 的所有质因子（可重复）。例如 $x=12$ 时，f[1]=2, f[2]=2, f[3]=3。
• a 数组则通过依次除以这些质因子，得到完整的路径序列：a = [12, 6, 3, 1]。
• cnt 记录的是质因子的总个数，也即从 $x$ 到 $1$ 的边的数量（路径长度）。

主函数中对于每组询问：

cpp
复制
1factorize(x, a, cnta);
2factorize(y, b, cntb);
3int px = 0, py = 0;
4while (a[px] != b[py]) {
5    if (a[px] > b[py]) px++;
6    else py++;
7}
8printf("%d\n", px + py);

双指针过程非常直观：因为序列从自身到根是递减的，所以数值较大的结点一定还在深处，需要向上移动；当两个指针指向的值相等时即到达 LCA。

---

时间复杂度分析

• 对于单个数 $n \le 10^9$，试除法分解质因数的时间复杂度为 $O(\sqrt{n})$，最坏约 $3 \times 10^4$ 次操作。
• 每组询问需要分解两个数，加上生成序列和双指针扫描（序列长度不超过 $30$），单次询问的复杂度为 $O(\sqrt{n})$。
• 总复杂度为 $O(q \sqrt{n})$。在题目的时间限制下，可以通过本题。
  （若 $q$ 很大，可改用预处理素数表来加速试除过程，进一步缩小常数。）

---

总结

本题的关键是发现树结构的规律：每个结点的父结点等同于除以它的最小质因子。于是问题转化为求两数的质因数分解序列，并找出它们序列的第一个公共元素（LCA）。利用双指针可以在线性时间内求出 LCA，再直接输出步数之和即为答案。这道题考察了对数论性质的理解以及将树上问题转化为序列问题的能力。