题解：AT_abc400_e [ABC400E] Ringo's Favorite Numbers 3

Emplace · 2025-04-06 12:33:54 · 题解

思路

分析

首先发现它是有多个询问，如果每个询问都去单独处理，很明显十分耗时间。所以预处理是个好东西，将所有数处理出来后再进行二分。

但是 A \le 10^{12} 该怎么办呢?可以发现它的要求是有两个质因子，且次数为偶数，那么肯定是一个平方数。那 10^{12} 以内肯定最多有 10^6 个这个数。

做法

最先想到的肯定是去枚举它的平方根。这个思路肯定是可以的。不过需要通过线性筛这个过程去线性分解质因数，比较复杂，而且我也不会写。所以这里可以考虑一种更加简单的方法。

我们可以先通过线性筛将 10^6 以内的质数筛出来。然后枚举每个质数，再枚举它的次数，随后再选择一个质数，再枚举这个质数的次数，就能将这种数一个个选出来。看起来时间复杂度很高，但是因为最多只有 10^6 个数，所以是没有问题的。

细节

• 在累加次数时要开 int128，不然是存不下的。
• 在第一个质数累加次数与选第二个质数时要在求不出答案时及时退出，不然会超时。
• 求完后要对存数的数组排序，因为用这种方法求序列是无序的，无法进行二分。

具体操作方式见代码。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int vis[2000000],a[2000000],id,q;
vector<int> p;
void pri(int n){
    for(int i=2;i<=n;i++){
        if(!vis[i]){
            p.push_back(i);
        }
        for(int j=0;j<p.size();j++){
            int k=p[j];
            if(k*i>n) break;
            vis[k*i]=1;
            if(i%k==0){
                break;
            }
        }
    }
}
signed main(){
    pri(1000000);
    for(int i=0;i<p.size();i++){
        int k=p[i];
        __int128 cnt=k*k;//细节1
        while(cnt<=1000000000000){
            int zhiqiang=0;
            for(int j=i+1;j<p.size();j++){
                int h=p[j],luozhi=0;
                __int128 sum=h*h;//细节1
                while(cnt*sum<=1000000000000){
                    luozhi++,zhiqiang++;
                    a[++id]=cnt*sum;
                    sum*=h*h;
                }
                if(luozhi==0) break;//细节2
            }
            if(zhiqiang==0) break;//细节2
            cnt*=k*k;
        }
    }
    sort(a+1,a+1+id);//细节3
    cin>>q;
    while(q--){
        int x;
        cin>>x;
        int l=1,r=id,ans;
        while(l<=r){
            int mid=(l+r)/2;
            if(a[mid]<=x){
                ans=a[mid];
                l=mid+1;
            }
            else{
                r=mid-1;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}