結果

問題 No.3101 Range Eratosthenes Query
コンテスト
ユーザー Today03
提出日時 2025-04-15 05:29:43
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 446 ms / 3,000 ms
コード長 2,972 bytes
コンパイル時間 4,294 ms
コンパイル使用メモリ 292,124 KB
実行使用メモリ 61,024 KB
最終ジャッジ日時 2025-04-15 05:30:01
合計ジャッジ時間 16,934 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

#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)),(v).erase(unique(ALL(v)),v.end())
#define REP(i, n) for (int i=0; i<(int)(n); i++)
#define RNG(i, a, b, s) for (ll i=(ll)(a); (s)>0 ? i<(b) : i>(b); i+=(s))
#define chmax(a, b) ((a)<(b) ? ((a)=(b), 1) : 0)
#define chmin(a, b) ((a)>(b) ? ((a)=(b), 1) : 0)

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 ld=long double; using ull=uint64_t;
using VI=vector<int>; using VVI=vector<VI>; using VL=vector<ll>; using VVL=vector<VL>;
using PL=pair<ll,ll>; using VP=vector<PL>; using TL=tuple<ll,ll,ll>; using WG=vector<vector<pair<int,ll>>>;



/// @file abel.hpp
/// @brief 可換群
namespace Abel{
	/// @brief 和
	template<typename T>
	struct Sum{
		using Type=T;
		static Type id(){return T(0);}
		static Type op(const Type&a,const Type&b){return a+b;}
		static Type inv(const Type&x){return -x;}
	};

	/// @brief XOR
	template<typename T>
	struct Xor{
		using Type=T;
		static Type id(){return T(0);}
		static Type op(const Type&a,const Type&b){return a^b;}
		static Type inv(const Type&x){return x;}
	};
}


/// @brief Fenwick Tree
/// @tparam Abel 可換群
template<typename Abel=Abel::Sum<ll>>
struct FenwickTree{
	using Type=typename Abel::Type;

	FenwickTree()=default;

	/// @brief サイズ n のFenwick Treeを構築する
	FenwickTree(int n){
		this->n=n;
		dat.assign(n,Abel::id());
	}

	/// @brief i 番目の要素に対し v[i] <- op(v[i], x) と更新する
	/// @note O(log(N))
	void add(int i,Type x){
		i++;
		while(i<=n){
			dat[i-1]=Abel::op(dat[i-1],x);
			i+=i&-i;
		}
	}

	/// @brief 区間 [l, r) の群積を返す
	/// @note O(log(N))
	Type sum(int l,int r){return Abel::op(Abel::inv(sum(l)),sum(r));}

	/// @brief i 番目の要素を返す
	/// @note O(log(N))
	Type operator[](int i){return sum(i,i+1);}

	/// @brief 配列のサイズを返す
	int size(){return n;}

private:
	int n;
	vector<Type>dat;
	Type sum(int r){
		Type ret=Abel::id();
		while(r>0){
			ret=Abel::op(ret,dat[r-1]);
			r-=r&-r;
		}
		return ret;
	}
};


int main(){
    int Q; cin>>Q;
    const int mx=1e6+10;
    VI D(mx,1);
    for(int i=1; i<mx; i++)for(int j=i*2; j<mx; j+=i) D[j]=i;

    vector<TL> event;
    RNG(i,1,mx,1) event.push_back({D[i],-1,i});
    vector<PL> query(Q);
    REP(i,Q) cin>>query[i].first>>query[i].second, query[i].second++;
    REP(i,Q){
        auto [l,r]=query[i];
        event.push_back({l-1,1,i});
    }
    sort(ALL(event));

    VI ans(Q);
    FenwickTree<Abel::Sum<ll>> fen(mx);
    for(auto [x,t,i]:event){
        if(t==-1) fen.add(i,1);
        else{
            auto [l,r]=query[i];
            ans[i]=fen.sum(l,r);
            if(l==1) ans[i]=1;
        }
    }

    for(int x:ans) cout<<x<<'\n';
}
0