题解：P17733 [ICPC 2019 Xuzhou R] <3 numbers

wzh120609 · 2026-10-22 19:18:13 · 题解

题目大意

定义 <3 数为因数个数小于 3 的数，显然除了 1，所有 <3 数就是质数，只有 1 和本身共 2 个因数。那么给你一段区间，问其中 <3 数的占比是否 <\frac{1}{3}。

思路

非常简单，先欧拉筛一手质数，数据小就直接枚举，数据大再在线判断一下质数，这里解释一下代码中函数的原理。就是说质数（除了 2 和 3）都可表示为 6 的倍数 \pm1，这是一个小优化，剩下的就是正常判断了。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e4+5;
int n,m,T,l,r,phi[N],prime[N],tot,ans,vis[N];
bool isPrime(int num){
    if(num==2||num==3)return 1;
    if(num%6!=1&&num%6!=5)return 0;
    for(int i=5;i<=sqrt(num);i+=6){
        if(num%i==0||num%(i+2)==0)return 0;
    }
    return 1;
}
int main(){
    phi[1]=1;
    for(int i=2;i<=N;i++){
        if(!vis[i]){
            prime[++tot]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=tot;j++){
            if(i*prime[j]>N)break;
            vis[i*prime[j]]=1;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];break;
            }
            else phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
    cin>>T;
    while(T--){
        scanf("%d%d",&l,&r);
        if(r<=1000){
            int cnt=0;
            for(int i=l;i<=r;i++)if(!vis[i])cnt++;
            if(cnt*3<(r-l+1))cout<<"Yes\n";
            else cout<<"No\n";
        }
        else if(r-l>=11)cout<<"Yes\n";
        else{
            int cnt=0;
            for(int i=l;i<=r;i++)if(isPrime(i))cnt++;
            if(cnt*3<(r-l+1))cout<<"Yes\n";
            else cout<<"No\n";
        }
    }
    return 0;
}