CF1771C Hossam and Trainees

· · 题解

设 V 为值域，本题中 V=10^9。

只用考虑最终找到的 x 为质数的情况，因为若 x 合法，那么 x 的所有因数都合法。

  1. 当 x\le\sqrt{V} 时，这样的 x 大概只有 3000 多个，可以直接枚举每个 x，再枚举每个 a_i，若存在 \ge2 个 a_i 是 x 的倍数，则 x 合法。

  2. 当 x>\sqrt{V} 时，由于 x 一定是某个 a_i 的因数，而每个 a_i 最多只有一个 >\sqrt{V} 的质因数，若存在 \ge2 个 a_i 的 >\sqrt{V} 的质因数相同，那么这个因数就是一个合法的 x。

const int N=1e5+10,M=3.5e4+10;
int n,a[N],isp[M],pri[M],cnt,ans,num[M]; map<int,int> mp;

inline void preworks(){
    for(int i=2;i<M;++i){
        if(!isp[i]) pri[++cnt]=i;
        for(int j=1;j<=cnt&&i*pri[j]<M;++j){
            isp[i*pri[j]]=1;
            if(!(i%pri[j])) break;
        }
    }
}

signed main(){
    preworks();
    for(int T=read();T;--T){
        n=read(),mp.clear(),ans=0;
        for(int i=1;i<=n;++i) a[i]=read();
        for(int i=1;i<=n;++i){
            for(int j=1;j<=cnt&&pri[j]<=a[i];++j) // 处理 <=sqrt(V) 的因数。
                if(!(a[i]%pri[j])){
                    ++num[j];
                    while(!(a[i]%pri[j])) a[i]/=pri[j];
                }
            if(a[i]>1){
                // 剩下的就是那个大于 sqrt(V) 的因数。
                if(mp[a[i]]){ans=1;break;} mp[a[i]]=1;
            }
        }
        for(int i=1;i<=cnt;++i) ans|=(num[i]>=2),num[i]=0;
        puts(ans?"YES":"NO");
    }
    return 0;
}