結果

問題 No.3101 Range Eratosthenes Query
コンテスト
ユーザー Today03
提出日時 2025-04-11 22:29:07
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 985 ms / 3,000 ms
コード長 2,929 bytes
コンパイル時間 3,845 ms
コンパイル使用メモリ 283,088 KB
実行使用メモリ 263,744 KB
最終ジャッジ日時 2025-04-11 22:29:43
合計ジャッジ時間 21,879 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define ALL(x) (x).begin(),(x).end()
#define IO ios::sync_with_stdio(false),cin.tie(nullptr);
#define LB(v,x) (int)(lower_bound(ALL(v),x)-(v).begin())
#define UQ(v) sort(ALL(v)), erase(unique(ALL(v)),v.end())

template<typename T> bool chmax(T&a, const T&b){ if(a<b){ a=b; return true; } return false; }
template<typename T> bool chmin(T&a, const T&b){ if(b<a){ a=b; return true; } return false; }
template<typename T> using rpriority_queue=priority_queue<T,vector<T>,greater<T>>;
using ll=long long; const int INF=1e9+10; const ll INFL=4e18;
using VI=vector<int>; using VVI=vector<VI>; using VL=vector<ll>; using VVL=vector<VL>; using VS=vector<string>;
using PL=pair<ll,ll>; using VP=vector<PL>; using TL=tuple<ll,ll,ll>; using WG=vector<vector<pair<int,ll>>>;



/// @file mst.hpp
/// @brief マージソート木
template<typename T>
struct MergeSortTree{
	MergeSortTree()=default;

	/// @brief 配列 v からマージソート木を構築する
	MergeSortTree(const vector<T>&v){
		n=v.size();
		mx=*max_element(v.begin(),v.end()),mn=*min_element(v.begin(),v.end());
		dat=vector<vector<T>>(n<<1);
		for(int i=0;i<n;i++)dat[n+i]={v[i]};
		for(int i=n-1;i>0;i--){
			merge(
				dat[i<<1].begin(),dat[i<<1].end(),
				dat[i<<1|1].begin(),dat[i<<1|1].end(),
				back_inserter(dat[i]));
		}
	}

	/// @brief 区間 [l, r) に存在する val 未満の値の個数を返す
	/// @note O(log(N)^2)
	int count_lt(int l,int r,T val){
		l+=n,r+=n;
		int ret=0;
		while(l<r){
			if(l&1)ret+=search(l++,val);
			if(r&1)ret+=search(--r,val);
			l>>=1,r>>=1;
		}
		return ret;
	}

	/// @brief 区間 [l, r) に存在する val 以下の値の個数を返す
	/// @note O(log(N)^2)
	int count_le(int l,int r,T val){return count_lt(l,r,val+1);}

	/// @brief 区間 [l, r) に存在する val より大きい値の個数を返す
	/// @note O(log(N)^2)
	int count_gt(int l,int r,T val){return n-l-count_le(l,r,val);}

	/// @brief 区間 [l, r) に存在する val 以上の値の個数を返す
	/// @note O(log(N)^2)
	int count_ge(int l,int r,T val){return n-l-count_lt(l,r,val);}

	/// @brief 区間 [l, r) の小さい方から k 番目の値を返す
	/// @brief k は 1-indexed で与える
	/// @note O(log(N)^3)
	T kth(int l,int r,int k){
		T lo=mn-1,hi=mx+1;
		while(hi-lo>1){
			T mid=(hi+lo)/2;
			(count_lt(l,r,mid)>=k?hi:lo)=mid;
		}
		return lo;
	}

private:
	int n;
	vector<vector<T>>dat;
	int search(int i,T val){return lower_bound(dat[i].begin(),dat[i].end(),val)-dat[i].begin();}
	T mx,mn;
};




int main(){
	IO;
	const int mx=1e6+10;
	VL md(mx,1);

	for(ll i=2;i<mx;i++){
		if(md[i]==1){
			for(ll j=i*2;j<mx;j+=i) chmax(md[j],j/i);
		}
	}

	//[L,R)の中でL以上の数の個数
	MergeSortTree<ll>mst(md);

	int Q;cin>>Q;
	while(Q--){
		int l,r;cin>>l>>r;r++;
		if(l==1) cout<<1<<'\n';
		else cout<<mst.count_lt(l,r,l)<<'\n';
	}
}
0