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

noiiloveyou · 2025-06-30 10:20:55 · 题解

知识点

GESP 五级：因数（初等数论）。

GESP 六级：树（树的定义，构造与遍历）。

题目分析

注意：本文所说的最大因数不包含此数，最小因数不包含 1。

题意很容易理解，简单地说，就是把 x 或 y 修改为它的最大因数（它的父结点），一直到这两个数相等（找到了两数的最近公共祖先），统计找了多少次最大因数（到最近公共祖先的距离）即可。

问题 1：如何快速找到一个数（用 n 表示）的最大因数？

很简单，先找到 n 的最小因数，接着用 n 除以这个最小因数，得到的就是 n 的最大因数。容易发现，除 n 外，最小因数不会超过 \sqrt{n}，理由：假设 n 的最小因数超过 \sqrt{n}，那一定存在一个小于 \sqrt{n} 的因数，与它相乘为 n，矛盾。但因为最小因数不能为一（会发生死循环），所以如果我们发现 n 最小因数大于 \sqrt{n}，就可以直接断定：n 是个质数，最小因数为 n。

问题 2：应当先找 x 还是 y 的最大因数？

由于我们的目标是在一番操作后，x 与 y 相等（即找到了最近公共祖先），而最大因数严格小于原数，因此应当将 x 与 y 中的较大数设为它的最大因数。如果 x 与 y 任然不相等，就重复这一过程。记得统计次数哦。

代码实现

#include<bits/stdc++.h>
using namespace std;
int q;
int main(){
    cin>>q;
    int x,y;
    for(int i=0;i<q;++i){
        cin>>x>>y;
        int xmax=2,ymax=2,ans=0;
        //分别表示目前找到 x 的最小因数，y 的最小因数和答案

        //一直执行，直到 x 等于 y
        while(x!=y){
            //x 较大
            if(x>y){
                //找最小因数
                while(x%xmax!=0){
                    //若最小因数超过 sqrt(x)，直接断定
                    if(xmax>sqrt(x)){
                        xmax=x;
                        break;
                    }
                    //否则，尝试下一个数
                    ++xmax;
                }
                //得到 x 的最大因数
                x/=xmax;
                ++ans;
            }

            //y 较大，与上类似
            else{
                while(y%ymax!=0){
                    if(ymax>sqrt(y)){
                        ymax=y;
                        break;
                    }
                    ++ymax;
                }
                y/=ymax;
                ++ans;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}