結果
問題 | No.3101 Range Eratosthenes Query |
ユーザー |
![]() |
提出日時 | 2025-04-11 21:42:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 662 ms / 3,000 ms |
コード長 | 811 bytes |
コンパイル時間 | 4,105 ms |
コンパイル使用メモリ | 252,220 KB |
実行使用メモリ | 47,072 KB |
最終ジャッジ日時 | 2025-04-11 21:42:57 |
合計ジャッジ時間 | 15,788 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 24 |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 4000000000000000001LL int main(){ vector<int> ma(1000005,0); for(int i=1;i<ma.size();i++){ for(int j=i*2;j<ma.size();j+=i){ ma[j] = i; } } int q; cin>>q; vector<int> l(q),r(q); vector<vector<int>> is(1000005); rep(i,q){ cin>>l[i]>>r[i]; is[r[i]].push_back(i); is[l[i]-1].push_back(i); } vector<int> ans(q); fenwick_tree<int> F(1000005); rep(i,is.size()){ F.add(ma[i],1); rep(j,is[i].size()){ int ii = is[i][j]; int v = F.sum(0,l[ii]); if(r[ii]==i)ans[ii] += v; else ans[ii] -= v; } } rep(i,q){ cout<<ans[i]<<endl; } return 0; }