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.
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