题解：P17733 [ICPC 2019 Xuzhou R] <3 numbers
Trulymieyun
·
·
题解
不难看出“<3 数”构成的集合其实就是质数集 \cup \{1\}，所以就是在问你一个区间内质数占比是否 <\frac{1}{3}，可以考虑先欧拉质数筛预处理，但是对于
~~众所周知~~，质数有个特性就是越往后其占比越稀疏，而当 $L>10^6$ 或 $R>10^6$ 时其稀疏程度已经可以保证 $< \frac{1}{3}$ 了，但是此处还要特判极小区间长度 $1$，$2$，$3$ 的情况，此处可采用如下普通判断质数方式来逐个判断该极小区间内的质数。
```
bool isPrime(int x){
int sx=sqrt(x);
if(x<2) return false;
if(x==2) return true;
if(x%2==0) return false;
for(int i=3;i<=sx;i+=2){
if(x%i==0) return false;
}
return true;
}
```
该判断算法时间复杂度 $O(\sqrt{n})$。
综上，仅先质数筛处理 $[2,10^6]$，若 $\le 10^6$ 就先用 `lower_bound` 求出第一个区间内的质数，再往后判断筛出来的质数直到超出区间，统计看是否 $<\frac{1}{3}$ 即可。若 $>10^6$ 则先特判极小区间，其余情况均 $<\frac{1}{3}$，直接输出 `Yes`。
记得 $1$ 也是“$<3$ 数”。
完整代码如下。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define M 1000002
#define int long long
vector<int> primes;
bool noprime[M];
void p(){
for(int i=2;i<=M;i++){
if(!noprime[i]) {
primes.push_back(i);
}
for(auto p:primes){
if(i*p>M) break;
noprime[i*p]=true;
if(i%p==0) break;
}
}
}
bool isPrime(int x){
int sx=sqrt(x);
if(x<2) return false;
if(x==2) return true;
if(x%2==0) return false;
for(int i=3;i<=sx;i+=2){
if(x%i==0) return false;
}
return true;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
p();
while(T--){
int cnt=0;
int l,r,lr;
cin>>l>>r;
if(l<=1e6&&r<=1e6){
int di=lower_bound(primes.begin(),primes.end(),l)-primes.begin();
while(primes[di]<=r){
cnt++;
di++;
}
if(l==1) cnt++;
int x=r-l+1;
if(3*cnt<x) cout<<"Yes\n";
else cout<<"No\n";
}
else{
if(r-l+1==1){
if(isPrime(l)) cout<<"No\n";
else cout<<"Yes\n";
}
else if(r-l+1==2){
bool hf=false;
if(l%2) hf=!isPrime(l);
else hf=!isPrime(r);
if(hf) cout<<"Yes\n";
else cout<<"No\n";
}
else if(r-l+1==3){
bool hf=!isPrime(l) and !isPrime(l+1) and !isPrime(l+2);
if(hf) cout<<"Yes\n";
else cout<<"No\n";
}
else{
cout<<"Yes\n";
}
}
}
}
```
~~代码是队友码的所以和我码风差别很大。~~