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

Neri_qwq · 2025-06-30 09:25:52 · 题解

题目传送门。

前言

GESP 6 级真的好水啊，场上一个小时就出来了。

比 5 级简单。

upd on 2025.8.21，发现一个错误，更正。

题目思路

lca 最近公共祖先问题暴力即可通过的削弱版。

两个点在树上的距离，可以看作两个点到它们的最近公共祖先的距离之和。观察到数据范围小，每个节点的父节点的值最多是这个节点的 \frac{1}{2}，所以可以直接暴力模拟往上跳的过程，统计跳的次数之和，即为答案。

给出两个点 l 和 r，他们的父节点分别为 fl 和 fr，跳的过程如下：

• 当 l < r 时，l = fl。
• 当 l > r 时，r = fr 。
• 当 l = r 时，说明已经跳好，返回答案即可。

这样可以有效地求出最近公共祖先。

另外求父节点时运用了类似质数筛的思想，因为往后就重复了，所以枚举最小因数只需从 2 枚举到 \sqrt n 即可。注意判断为质数的情况，直接跳到根节点即可。

code

#include <bits/stdc++.h>
using namespace std;
int jump(int x)
{
    for (int i = 2; i <= sqrt(x); i++)
        if (x % i == 0)
            return x / i;
    return 1;
}
int lca(int l, int r)
{
    int cnt = 0;
    while (l != r)
    {
        if (l < r)
            r = jump(r);
        else
            l = jump(l);
        cnt++;
    }
    return cnt;
}
void solve()
{
    int q;
    cin >> q; 
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        cout << lca(l, r) << "\n";
    }
}
int main()
{
    solve();
    return 0;
}