【代码源每日一题div1 二分答案】质区间长度

忘是亡心i 2024-03-26 19:18 63阅读 0赞

**写一下之前写过的题的题解**

**感觉篮球杯难度**

[质区间长度 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge]

题意：

![96daff4d64a3f9e2c83acedaef6d1c6e.png][]

思路：

注意数据范围是1e6，因此我们是可以去暴力前缀和的

注意到len具有二段性，即len大的时候一定是个质区间,len足够小的时候一定不是，因此直接去二分len就行，check的时候就去扫一遍就好了

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=1e6+10,mxv=1e6+10;
    int L,R,k,len=0,ans=-1;
    int vis[mxn],prime[mxn],pre[mxn];
    void init(int n){
        for(int i=2;i<=n;i++){
            if(!vis[i]) prime[++len]=i;
            for(int j=1;prime[j]<=n/i;j++){
                vis[i*prime[j]]=1;
                if(i%prime[j]==0) break;
            }
        }
    }
    bool check(int len){
        for(int x=L;x<=R-len+1;x++){
            if(pre[x+len-1]-pre[x-1]<k) return false;
        }
        return true;
    }
    int main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        init(1e6);
        cin>>L>>R>>k;
        if(k==0){
            cout<<1<<'\n';
            return 0;
        }
        for(int i=L;i<=R;i++){
            if(!vis[i]) pre[i]=pre[i-1]+1;
            else pre[i]=pre[i-1];
        }
        int l=1,r=R-L+1;
        while(l<=r){
            int mid=l+r>>1;
            if(check(mid)){
                ans=mid;
                r=mid-1;
            }else l=mid+1;
        }
        if(ans==R-L+1) cout<<-1<<'\n';
        else cout<<ans<<'\n';
    }

[- _ - Daimayuan Online Judge]: http://oj.daimayuan.top/course/10/problem/737
[96daff4d64a3f9e2c83acedaef6d1c6e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/cc1fc2265bd14dcfbce6eaf12002cb5b.png