专栏文章

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

SS_Y_B_S
P13016题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mip0l3qd
此快照首次捕获于
2025/12/03 04:12
3 个月前
此快照最后确认于
2025/12/03 04:12
3 个月前
查看原文

P13016 最大因数 题解

思路

60pts

强模拟即可，核心代码如下：
CPP
int ans = 0;
while(x!=y){
  if(x<y) swap(x,y);
  for(int i = x-1;i;i--){
      if(x%i==0){
          ans++,x=i;
          break;
      }
  }
}

100pts

看到数据范围 1≤xi,yi≤1091 \le x_i,y_i \le 10^9，考虑得到一个稍微合理的时间复杂度。
所以我们要对寻找最大因数的部分进行优化。
我们可以发现在寻找因数时，若直接枚举寻找最大因数，复杂度是 O(n)O(n) 级别的，但是我们如果通过寻找最小因数，再用原数除以最小因数的方法得到最大因数，复杂度则是 O(n)O(\sqrt{n}) 级别的。
but 这样仍是 60pts，于是寻找复杂度瓶颈。
可以发现当 xix_i 或 yiy_i 为质数时，寻找最大因数的时间复杂度仍是 O(n)O(n) 的。
又因为根据题意，编号为质数的父结点一定为 1。
所以在每次操作时进行一次质数判断即可。
时间复杂度 O(qWlog⁡W)O(q\sqrt{W}\log W)（W 为值域），完结撒花（什么逆天复杂度）。

AC code

CPP
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int q,x,y;
bool isprime(int a){
    for(int i = 2;i*i<=a;i++)
        if(a%i==0)
            return 0;
    return 1;
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>q;
    while(q--){
        cin>>x>>y;
        int ans = 0;
        while(x!=y){
            if(x<y) swap(x,y);
            if(isprime(x)){
                ans++,x=1;
                continue;
            }
            for(int i = 2;;i++){
                if(x%i==0){
                    ans++,x/=i;
                    break;
                }
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...