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

· · 题解

Solution

我们直接来看一下这道题。题目让我们判断 L 到 R 之间 <3 数的比例是否小于三分之一。

而 <3 数 的定义如下：

这让我们第一时间想起所有的质数都属于 <3 数 , 所以这道题就可以轻而易举的做出来了：求质数 , 判断范围内质数的个数 , 输出

但是 , 题目的范围是 1 \le L \le R \le 10^9 , 不能一个个列质数 , 而且数字 1 也属于 <3 数 , 所以 , 我们只能从密度小于 \dfrac13 下手。

质数在所有正整数里的占比遵循以下公式：

\frac{\pi(N)}{N} \approx \frac{1}{\ln N}

N 变大 , 质数占比慢慢变小。所以当一个范围内的数足够多时 , 那密度一定小于 \dfrac13 。

代码如下：

::::success[Code]

#include<bits/stdc++.h>
using namespace std;
int t , l , r , len;
bool z(long long a){
    if(a<2)return false;
    if(a==2 || a==3)return true;
    if(a%2==0)return false;
  if(a%3==0)return false;
    for(int i=2;i*i<=a;i++){
        if(a%i==0) return false;
    }return true;
}
int main(){
    cin>>t;
    while(t--){
        cin>>l>>r;
        len=r-l+1;
        int x=0;
        if(r-l+1>500){
            cout<<"Yes\n";
            continue;
        }for(int i=l;i<=r;i++){
            if(i==1||z(i)){
                x++;
            }
        }
        if (3*x<len){
            cout<<"Yes\n";
        }else{
            cout<<"No\n";
        }
    }
    return 0;
}

::::