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

· · 题解

P13016 最大因数 题解

思路

60pts

强模拟即可，核心代码如下：

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 \le x_i,y_i \le 10^9，考虑得到一个稍微合理的时间复杂度。

所以我们要对寻找最大因数的部分进行优化。

我们可以发现在寻找因数时，若直接枚举寻找最大因数，复杂度是 O(n) 级别的，但是我们如果通过寻找最小因数，再用原数除以最小因数的方法得到最大因数，复杂度则是 O(\sqrt{n}) 级别的。

but 这样仍是 60pts，于是寻找复杂度瓶颈。

可以发现当 x_i 或 y_i 为质数时，寻找最大因数的时间复杂度仍是 O(n) 的。

又因为根据题意，编号为质数的父结点一定为 1。

所以在每次操作时进行一次质数判断即可。

时间复杂度 O(q\sqrt{W}\log W)（W 为值域），完结撒花（什么逆天复杂度）。

AC code

#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;
}