AT_abc400_e 题解

ikunTLE · 2025-04-04 00:00:13 · 题解

题目传送门

思路

首先打个埃氏筛，统计出每个数不同素因数的个数，计入数组 C 中。

然后遍历一遍，用数组 R 统计，R_i 表示不超过 i 的最大的恰好有两个不同的素因数。令 P=0，遍历时，若有 C_i=2，则说明 i 恰好有两个不同的素因数，更新 P=i。每一次遍历无论是否更新 P，都要记 R_i=P。

查询的时候，答案即为 R_{\lfloor\sqrt{A}\rfloor}^2。这是因为 R 中储存的是恰好有两个不同的素因数，平方后即为答案。

时间复杂度 \mathcal{O}(N\log\log N)，是埃氏筛的复杂度。

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=1e6;
int cnt[N+10],res[N+10];
void _init(){
    for(int i=2;i<=N;++i)
        if(!cnt[i])
            for(int j=i;j<=N;j+=i)
                ++cnt[j];
    int p=0;
    for(int i=1;i<=N;++i){
        if(cnt[i]==2)
            p=i;
        res[i]=p;
    }
    return;
}
signed main(){
    _init();
    int q=read();
    while(q--){
        int a=read();
        int sq=sqrt(a);
        while(sq*sq>a)
            --sq; // 控制精度
        printf("%lld\n",res[sq]*res[sq]);
    }
    return 0;
}