G6016 [GESP202506 六级] 最大因数 题解

知识点：树上路径、质因数分解、数学建模。

解题思路

把每个整数的父节点定义为最大真因数，即除以最小质因数。两个数不同时，始终把较大者移到父节点，累计步数直到相遇。

为什么正确

父节点严格小于自身，较大当前节点不可能是较小节点的祖先；先提升较大者不会越过共同祖先，最终相遇得到树上最短路径。

易错点

质数的父节点是1；1不能继续向上；不能用“最大质因数”代替最大真因数。

复杂度

单次试除O(√A)，每组保守O(√A log A)，空间O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    auto parent=[](long long x) {
        for(long long p=2;p*p<=x;p++)if(x%p==0)return x/p;
        return 1LL;
    }
    ;
    int q;
    cin>>q;
    while(q--) {
        long long x,y;
        cin>>x>>y;
        int ans=0;
        while(x!=y) {
            if(x>y)x=parent(x);
            else y=parent(y);
            ans++;
        }
        cout<<ans<<"\n";
    }
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。