結果
問題 | No.3101 Range Eratosthenes Query |
ユーザー |
|
提出日時 | 2025-04-11 22:23:59 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 701 ms / 3,000 ms |
コード長 | 1,817 bytes |
コンパイル時間 | 1,929 ms |
コンパイル使用メモリ | 180,776 KB |
実行使用メモリ | 154,100 KB |
最終ジャッジ日時 | 2025-04-11 22:24:20 |
合計ジャッジ時間 | 17,145 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 24 |
コンパイルメッセージ
main.cpp: In function ‘int32_t main()’: main.cpp:54:14: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions] 54 | for(auto [l,r]:que) | ^
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long const int p=998244353; int po(int a,int b) {if(b==0) return 1; if(b==1) return a; if(b%2==0) {int u=po(a,b/2);return (u*1LL*u)%p;} else {int u=po(a,b-1);return (a*1LL*u)%p;}} int inv(int x) {return po(x,p-2);} mt19937 rnd; #define app push_back #define all(x) (x).begin(),(x).end() #ifdef LOCAL #define debug(...) [](auto...a){ ((cout << a << ' '), ...) << endl;}(#__VA_ARGS__, ":", __VA_ARGS__) #define debugv(v) do {cout<< #v <<" : {"; for(int izxc=0;izxc<v.size();++izxc) {cout << v[izxc];if(izxc+1!=v.size()) cout << ","; }cout <<"}"<< endl;} while(0) #else #define debug(...) #define debugv(v) #endif #define lob(a,x) lower_bound(all(a),x) #define upb(a,x) upper_bound(all(a),x) const int maxn=2e6+5; int mi[maxn];int ma[maxn]; int fe[maxn]; vector<int> pos[maxn]; void add(int pos) {while(pos<maxn) {fe[pos]++;pos|=(pos+1);}} int get(int pos) {int ans=0;while(pos>=0) {ans+=fe[pos];pos&=(pos+1);--pos;} return ans;} int32_t main() { ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); fill(mi,mi+maxn,1e18); mi[1]=1;ma[1]=1; for(int i=2;i<maxn;++i) { for(int j=i;j<maxn;j+=i) { mi[j]=min(mi[j],i); } } for(int i=2;i<maxn;++i) { ma[i]=i/mi[i];pos[ma[i]].app(i); } pos[1].app(1); int t;cin>>t; vector<pair<int,int> > que,que1; while(t--) { int l,r;cin>>l>>r; que1.app({l,r}); } que=que1; sort(all(que)); map<pair<int,int>,int> res; int cur=0; for(auto [l,r]:que) { while(cur<l) { for(int j:pos[cur]) {add(j);} ++cur; } res[{l,r}]=max(1LL,get(r)-get(l-1)); } for(auto h:que1) { cout<<res[h]<<'\n'; } return 0; }