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

· · 题解

更好的观感体验。

题目分析

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

观察

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

质数的父节点是 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)。

最后，欢迎来到我的博客玩。