Editorial for Bedao Grand Contest 01 - KPRIME


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Code mẫu

#include <bits/stdc++.h>
using namespace std;
#define maxn 10000007
#define forinc(i,a,b) for(int i=a;i<=b;i++)
#define fordec(i,a,b) for(int i=a;i>=b;i--)
#define checkfile(FiLeNaMe) { if(fopen(FiLeNaMe".inp","r")) freopen(FiLeNaMe".inp","r",stdin),freopen(FiLeNaMe".out","w",stdout); }
///>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
int n,k;
bitset<maxn> prime;
int sum[maxn];

void enter(){
    cin>>n>>k;
}

void solve(){
    prime[0]=prime[1]=0;
    forinc(i,2,n) prime[i]=1;
    for(int i=2;i*i<=n;i++) if(prime[i]) for(int j=i*i;j<=n;j+=i) prime[j]=0;

    int64_t ans=0;

    for(int l=1,r=0,cnt=0;l<=n;l++){
        while(r<=n && cnt<k) cnt+=prime[++r];

        if(r>n) break;

        ans+=n-r+1;

        cnt-=prime[l];
    }

    cout<<ans;
}

signed main(){
    checkfile("KPRIME");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    enter();
    solve();

    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.