結果

問題 No.3101 Range Eratosthenes Query
ユーザー Tourmaline
提出日時 2025-04-11 21:39:40
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 469 ms / 3,000 ms
コード長 4,873 bytes
コンパイル時間 5,963 ms
コンパイル使用メモリ 333,292 KB
実行使用メモリ 46,232 KB
最終ジャッジ日時 2025-04-11 21:39:56
合計ジャッジ時間 16,119 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

#include <atcoder/all>

using namespace std;
using namespace atcoder;

using ll=long long;
using LL=__int128;
using ld=long double;
using uint=unsigned int;
using ull=unsigned long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
template<typename T> using vc=vector<T>;
template<typename T> using vvc=vector<vc<T>>;
template<typename T> using vvvc=vector<vvc<T>>;
using vi=vc<int>;
using vvi=vvc<int>;
using vd=vc<ld>;
using vvd=vvc<ld>;
using vl=vc<ll>;
using vvl=vvc<ll>;
using vs=vc<string>;
using vp=vc<pll>;
using vvp=vvc<pll>;

#define overload3(_1,_2,_3,name,...) name
#define rep1(n) for(ll _=0;_<ll(n);_++)
#define rep2(i,n) for(ll i=0;i<ll(n);i++)
#define rep3(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define rep(...) overload3(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(n) for(ll _=ll(n);_--;)
#define rrep2(i,n) for(ll i=ll(n);i--;)
#define rrep3(i,a,b) for(ll i=ll(b);i-->ll(a);)
#define rrep(...) overload3(__VA_ARGS__,rrep3,rrep2,rrep1)(__VA_ARGS__)

#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()

template<int m>
ostream& operator<<(ostream& os,static_modint<m> v){
	os<<v.val();
	return os;
}
istream& operator>>(istream& is,__int128& v){
    string s;
    is>>s;
    v=0;
	rep(i,s.size())if(isdigit(s[i])) v=v*10+s[i]-'0';
	if(s[0]=='-') v*=-1;
    return is;
}
ostream& operator<<(ostream& os,__int128 v){
	ostream::sentry s(os);
	if(s){
		__uint128_t t=v<0?-v:v;
		char buf[128];
		char* d=end(buf);
		do{
			d--;
			*d="0123456789"[t%10];
			t/=10;
		}while(t);
		if(v<0){
			d--;
			*d='-';
		}
		int len=end(buf)-d;
		if(os.rdbuf()->sputn(d,len)!=len) os.setstate(ios_base::badbit);
	}
	return os;
}
template<typename S,typename T>
ostream& operator<<(ostream& os,pair<S,T> a){
	os<<a.first<<' '<<a.second;
	return os;
}
template<typename T>
ostream& operator<<(ostream& os,vector<T> a){
	if(a.empty()) return os;
	os<<a[0];
	rep(i,1,a.size()) os<<' '<<a[i];
	return os;
}
template<typename T>
ostream& operator<<(ostream& os,vector<vector<T>> a){
	if(a.empty()) return os;
	os<<a[0];
	rep(i,1,a.size()) os<<endl<<a[i];
	return os;
}
void output(auto x){cout<<x<<endl;}
template<typename T>
void output(vector<T> a,bool next_line=0){
	if(next_line){
		for(auto x:a) output(x);
	}
	else cout<<a<<endl;
}

void debug(auto ...vs){
	((cout<<vs<<", "),...)<<endl;
}

void syosu(int x=15){cout<<fixed<<setprecision(x);}
void YN(bool x){cout<<(x?"Yes":"No")<<endl;}
void chmin(auto &x,auto y){if(x>y) x=y;}
void chmax(auto &x,auto y){if(x<y) x=y;}

template<typename T>
void read(vector<T> &a,int n,int off=0){
	a=vector<T>(n);
	for(auto &i:a){
		cin>>i;
		i-=off;
	}
}

void read(vs &a,int n){
	a=vs(n);
	for(auto &i:a) cin>>i;
}

template<typename T>
void read(vector<pair<T,T>> &a,int n,int off=0){
	a=vector<pair<T,T>>(n);
	for(auto &[x,y]:a){
		cin>>x>>y;
		x-=off,y-=off;
	}
}

template<typename T>
void read(vector<vector<T>> &a,int n,int m,int off=0){
	a=vector<vector<T>>(n,vector<T>(m));
	for(auto &i:a) for(auto &j:i){
		cin>>j;
		j-=off;
	}
}

template<typename T>
void readGraph(vector<vector<T>> &g,int n,int m,bool rv=1,int off=1){
	g=vector<vector<T>>(n);
	for(int i=0;i<m;i++){
		T u,v;
		cin>>u>>v;
		u-=off,v-=off;
		g[u].emplace_back(v);
		if(rv) g[v].emplace_back(u);
	}
}

template<typename T>
void readGraph(vector<vector<pair<T,T>>> &g,int n,int m,bool id=0,bool rv=1,int off=1){
	g=vector<vector<pair<T,T>>>(n);
	for(int i=0;i<m;i++){
		if(id){
			T u,v;
			cin>>u>>v;
			u-=off,v-=off;
			g[u].emplace_back(v,i);
			if(rv) g[v].emplace_back(u,i);
		}
		else{
			T u,v,w;
			cin>>u>>v>>w;
			u-=off,v-=off;
			g[u].emplace_back(v,w);
			if(rv) g[v].emplace_back(u,w);
		}
	}
}

string toBinary(ll x,ll n,bool rev=0){
	assert(0<=x&&x<1LL<<n);
	string s(n,'0');
	for(int i=0;i<n;i++) if(x&1LL<<i) s[n-i-1]='1';
	if(rev) reverse(s.begin(),s.end());
	return s;
}

constexpr ll inf=1<<30;
constexpr ll INF=1ll<<60;
const ld pi=acosl(-1);
constexpr ld eps=1e-9;
//constexpr ll mod=1e9+7;
constexpr ll mod=998244353;
constexpr int dx[9]={-1,0,1,0,1,1,-1,-1,0};
constexpr int dy[9]={0,1,0,-1,1,-1,1,-1,0};

using mint=static_modint<mod>;
using vm=vc<mint>;
using vvm=vvc<mint>;

void main2();

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	ll q=1;
//	cin>>q;
	while(q--) main2();
}

const ll M=1e6;

void main2(){
	ll q;
	cin>>q;
	struct squery{
		ll l,r,id;
	};
	vc<squery> qs(q);
	rep(i,q){
		ll l,r;
		cin>>l>>r;
		r++;
		qs[i]=squery{l,r,i};
	}
	sort(ALL(qs),[&](squery x,squery y){
		return x.l>y.l;
	});
	vl rs(q);
	vvl g(M+1);
	ll I=0;
	vi ud(M+1,1);
	fenwick_tree<ll> st(M+1);
	rrep(x,1,M+1){
		st.add(x,1);
		for(ll y=2*x;y<=M;y+=x)if(ud[y]){
			ud[y]=0;
			st.add(y,-1);
		}
		while(I<q&&qs[I].l==x){
			rs[qs[I].id]=st.sum(qs[I].l,qs[I].r);
			I++;
		}
	}
	output(rs,1);
}
0