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

fuyixiang · 2026-10-22 19:14:59 · 题解

前言

听了同机房大佬们的思路，感觉还是太吃思维了。

这里提供一个可以近乎于无脑的做法。

解题思路

首先，可以发现题目中所说的“ <3 数”实质上是 1 或者质数。

思考如何找出区间范围内的“ <3 数”的数量。

先考虑线性做法，即约束条件改为 1 \le L \le R \le 10^7。

这时，容易想到使用线性筛筛出 [1,10^7] 内的所有“ <3 数”，再使用二分查找即可。

然后，考虑 R > 10^7 的情况。

:::info[素数出现占比]{open} 通常，在算法竞赛中使用 \pi(x) 表示小于或等于 x 的素数的个数。

随着 x 的增大，\pi(x) 有近似结果 \pi(x)=\frac{x}{\ln x}。

可知，随着 x 的增大，素数的分布越来越稀疏。

也就是说，对于相同的囊括的数字数量，位置越靠后，比例小于三分之一的可能就越大。

实际上，根据笔者在赛时的测试，对于 R > 10^7 的部分，若询问的区间所囊括的数字数量大于 20，则比例一定小于三分之一。

对于剩下的部分，可枚举并使用试除法判断并统计。

这样，就使用了一种分治的思想解决了本题。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e7+10;
int pos;
int prime[N];
bool flag[N];
void init_prime(){
    prime[++pos]=1;
    for(int i=2;i<=N-10;i++){
        if(!flag[i]) prime[++pos]=i;
        for(int j=2;j<=pos;j++){
            if(i*prime[j]>N-10) break;
            flag[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
}
bool check(int x){
    for(int i=2;i<=sqrt(x);i++){
        if(x%i==0) return false;
    }
    return true;
}
int t,l,r;
int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);  cout.tie(0);
    init_prime();
    cin>>t;
    while(t--){
        cin>>l>>r;
        if(r<=N-10){
            int L=lower_bound(prime+1,prime+pos+1,l)-prime;
            int R=upper_bound(prime+1,prime+pos+1,r)-prime;
            if(3*(R-L)<r-l+1) cout<<"Yes\n";
            else cout<<"No\n";
        }else{
            if(r-l+1>20) cout<<"Yes\n";
            else{
                int cnt=0;
                for(int i=l;i<=r;i++) cnt+=check(i);
                if(cnt*3<r-l+1) cout<<"Yes\n";
                else cout<<"No\n";
            }
        }
    }
    return 0;
}