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

Enoch2013 · 2025-06-30 16:19:52 · 题解

前言

这其实挺简单的（我赛时用了不到八分钟就通过了）。

思路

对于每个节点 k，我们要寻找它的父亲，我们可以找到它的最小因数 p，然后 k \div p 即可得到父亲，代码如下：

int get_fa(int x) // 寻找节点x的父亲
{
    int res = 0;
    for (int i = 2; i <= x / i; i++) if (!(x % i)) { res = i; break; } // 找到最小因数（从2开始算）
    if (res == 0) res = 1; // 如果x为质数，将它的父亲设为1
    else res = x / res; // 得到最大因数（注意：最大因数不包含x本身）
    return res;
}

对于节点 x 和节点 y，我们将它们之间的路径记为 x \rightarrow lca_{x, y} \rightarrow y，长度为 cnt_{x \rightarrow lca_{x, y}} + cnt_{lca_{x, y} \rightarrow y}，我们可以一边寻找 lca_{x,y} 一边计算路径长度即可，代码如下：

int get_ans(int x, int y)
{
    int cnt_x = 0, cnt_y = 0;
    if (x == y) return 0; // 如果相等，无需计算
    if (x > y) swap(x, y); // 保证y的深度大于x
    while (x != y) // 一步一步往上爬
        if (y > x) y = get_fa(y), cnt_y++; // 边爬边计算
        else x = get_fa(x), cnt_x++; // 边爬边计算
    return cnt_x + cnt_y; // 返回总长
}

最后附上无注释的代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int q, x, y;
int get_fa(int x)
{
    int res = 0;
    for (int i = 2; i <= x / i; i++) if (!(x % i)) { res = i; break; }
    if (res == 0) res = 1;
    else res = x / res;
    return res;
}
int get_ans(int x, int y)
{
    int cnt_x = 0, cnt_y = 0;
    if (x == y) return 0;
    if (x > y) swap(x, y);
    while (x != y)
        if (y > x) y = get_fa(y), cnt_y++;
        else x = get_fa(x), cnt_x++;
    return cnt_x + cnt_y;
}
signed main()
{
    cin >> q;
    while (q--)
    {
        cin >> x >> y;
        cout << get_ans(x, y) << endl;
    }
    return 0;
}