LightOJ – Help Hanzo

L
Problem NameHelp Hanzo
JudgeLightOJ
Problem Linkhttps://lightoj.com/problem/help-hanzo
Algorithms & DSSegmented Sieve
#include<bits/stdc++.h> using namespace std; typedef long long ll; constexpr ll MX = 100000; bitset<100010>bs; vector<ll>primes; void sieve() { bs.set(); bs[0]=bs[1]=0; primes.push_back(2); for(ll i=4;i<=MX;i+=2)bs[i]=0; for(ll i=3;i<=MX;i+=2){ if(bs[i]==1){ primes.push_back(i); for(ll j=i*i;j<=MX;j+=i)bs[j]=0; } } } int main() { sieve(); ll len=primes.size(); ll t; ll l, r; cin>>t; for(ll T=1; T<=t;T++){ cin>>l>>r; bitset<100005>newbs; newbs.set(); for(ll i=0;i<len;i++){ ll val=l/primes[i]; if(l%primes[i]!=0)val++; val*=primes[i]; if(l==0){ newbs[0]=newbs[1]=0; }else if(l==1){ newbs[0]=0; } if(val==primes[i])val+=primes[i]; for(ll j=val;j<=r;j+=primes[i]){ newbs[j-l]=0; } } ll ans=0; for(ll i=0;i<=(r-l);i++)if(newbs[i])ans++; cout<<"Case "<<T<<": "; cout<<ans<<"\n"; } return 0; }
Code language: PHP (php)

About the author

আবু রিফাত মুহাম্মদ

সখের বশে প্রোগ্রামিং করি। নতুন নতুন জিনিস শিখতে এবং শেখাতে ভালবাসি।

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments

আবু রিফাত মুহাম্মদ

সখের বশে প্রোগ্রামিং করি। নতুন নতুন জিনিস শিখতে এবং শেখাতে ভালবাসি।

যোগাযোগ করুন

error: Alert: Content is protected !!