题解：P13016 [GESP202506 六级] 最大因数

更洛谷的观感体验

题目分析

这道题说了一棵特殊的树，其中每个节点 $k$（$2\leq k$）的父节点是 $k$ 的最大真因数（$k$ 的因数中除了 $k$ 本身外最大的因数）。根节点是 $1$。要处理多个查询，每个查询给出两个节点编号 $x$ 和 $y$，需要计算它们在树上的距离（即连接路径的边数）。

观察

每个节点的父节点是其最大真因数。例如：

• 节点 $3$ 的父节点是 $1$（因为 $3$ 的因数是 $1,3$，最大真因数是 $1$）
• 节点 $8$ 的父节点是 $4$（$8$ 的因数是 $1,2,4,8$，最大真因数是 $4$）
• 节点 $15$ 的父节点是 $5$（$15$ 的因数是 $1,3,5,15$，最大真因数是 $5$）

质数的父节点是 $1$，因为质数的最大真因数只能是 $1$。

思路

对于每个查询 $(x,y)$，我们可以分别计算 $x$ 和 $y$ 到根节点1的路径，然后找到它们的最近公共祖先(LCA)，最后计算距离。

步骤：

1. 实现一个函数 get_parent(k)，返回 $k$ 的最大真因数
2. 对于 $x$ 和 $y$，分别向上遍历到根节点，记录路径
3. 找到 $x$ 和 $y$ 路径上的最后一个公共节点（LCA）
4. 计算 $x$ 到 LCA 的距离和 $y$ 到 LCA 的距离之和

代码

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

// 获取k的最大真因数
int get_parent(int k)
{
    if (k == 1) return 0; //根节点没有父节点
    for (int i = 2; i * i <= k; i++)
        if (k % i == 0)
            return k / i; //返回最大真因数
    return 1; // k是质数，父节点是1
}

// 获取从k到根的路径
vector<int> get_path(int k)
{
    vector<int> path;
    while (k != 0)
        path.push_back(k), k = get_parent(k);
    return path;
}

// 计算两点的距离
int get_d(int x, int y)
{
    vector<int> path_x = get_path(x);
    vector<int> path_y = get_path(y);
    
    // 找到LCA
    int i = path_x.size() - 1;
    int j = path_y.size() - 1;
    while (i >= 0 && j >= 0 && path_x[i] == path_y[j]) {
        i--;
        j--;
    }
    
    return (i + 1) + (j + 1);
}

int main()
{
    int q;
    cin >> q;
    while (q--)
{
        int x, y;
        cin >> x >> y;
        cout << get_d(x, y) << endl;
    }
    return 0;
}

复杂度分析

时间复杂度：每个查询的最坏情况是 $O(\sqrt{\smash[b]{x}} + \sqrt{\smash[b]{y}})$。因为 $q\leq1000$ 和 $x,y\leq 10^9$，所以可以过。

空间复杂度：主要消耗在存储路径上，最坏情况下路径长度是$O(\log k)$。