結果
問題 | No.1657 Sum is Prime (Easy Version) |
ユーザー | 👑 CleyL |
提出日時 | 2024-01-24 12:34:40 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 5,760 bytes |
コンパイル時間 | 1,633 ms |
コンパイル使用メモリ | 145,040 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-28 07:05:48 |
合計ジャッジ時間 | 2,595 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 4 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 1 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 4 ms
5,376 KB |
testcase_13 | AC | 3 ms
5,376 KB |
testcase_14 | AC | 5 ms
5,376 KB |
testcase_15 | AC | 4 ms
5,376 KB |
testcase_16 | AC | 3 ms
5,376 KB |
testcase_17 | AC | 3 ms
5,376 KB |
testcase_18 | AC | 4 ms
5,376 KB |
testcase_19 | AC | 3 ms
5,376 KB |
testcase_20 | AC | 3 ms
5,376 KB |
testcase_21 | AC | 3 ms
5,376 KB |
testcase_22 | AC | 3 ms
5,376 KB |
testcase_23 | AC | 5 ms
5,376 KB |
ソースコード
//yukicoder@cpp17 #include <iostream> #include <iomanip> #include <algorithm> #include <cmath> #include <cctype> #include <climits> #include <cassert> #include <string> #include <vector> #include <set> #include <stack> #include <queue> #include <map> #include <random> #include <bitset> #include <complex> #include <utility> #include <numeric> #include <functional> using namespace std; using ll = long long; using P = pair<ll,ll>; const ll MOD = 998244353; const ll MODx = 1000000007; const int INF = (1<<30)-1; const ll LINF = (1LL<<62LL)-1; const double EPS = (1e-10); P ar4[4] = {{0,1},{0,-1},{1,0},{-1,0}}; P ar8[8] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}; template <typename T> vector<T> make_vector(size_t a, T b) { return vector<T>(a, b); } template <typename... Ts> auto make_vector(size_t a, Ts... ts) { return vector<decltype(make_vector(ts...))>(a, make_vector(ts...)); } /* 確認ポイント cout << fixed << setprecision(n) << 小数計算//n桁の小数表記になる 計算量は変わらないが楽できるシリーズ min(max)_element(iter,iter)で一番小さい(大きい)値のポインタが帰ってくる count(iter,iter,int)でintがiterからiterの間にいくつあったかを取得できる */ /* function corner below */ /* Function corner above */ /* comment outed because can cause bugs __attribute__((constructor)) void initial() { cin.tie(0); ios::sync_with_stdio(false); } */ template<typename T> struct BIT{//1_Indexed int n; vector<T> bit; BIT(){} BIT(int n_):n(n_+1),bit(n,0){} void set(int n_){ n = n_; bit.assign(n,0); } T sum(int a){ T ret = 0; for(int i = a; i > 0; i -= i & -i) ret += bit[i]; return ret; } void add(int a,T w){ for(int i = a; i <= n; i += i & -i)bit[i] += w; } T query(int r,int l){ return sum(l-1)-sum(r-1); } int lower_bound(T x){ if(x <= 0){ return 0; } x--; int t = 1; while(t < n)t <<= 1; int st = 0; int base = 0; for(; t; t/=2){ if(st+t <= n && base+bit[st+t] <= x){ base += bit[st+t]; st += t; } } return st+1; } }; struct SieveEratos{ int N; vector<int> minp; vector<int> primes; map<int,int> invprimes; SieveEratos(){} SieveEratos(int n):N(n+1){ generate(); } void set(int n){ N = n; generate(); } void generate(){ minp.assign(N+1, N+2); minp[0] = minp[1] = -1; for(int i = 2; N >= i; i++){ if(minp[i] == N+2){ primes.push_back(i); invprimes[i] = primes.size(); minp[i] = i; for(int j = i+i; N >= j; j+=i){ minp[j] = min(i, minp[j]); } } } } bool operator[](int x){return minp[x] == x;} }; // 整数型を取得することを想定 template <typename T> T CeilExactSqrt(int c, T x){ T mn = 0; T mx = x; while(mx-mn > 1){ T ce = (mn+mx)/2; T nw = 1; for(int i = 0; c > i; i++){ if(x/ce < nw){ mx = ce; break; } nw *= ce; if(i+1 == c && x == nw){ mx = ce; } } if(mx != ce)mn = ce; } return mx; } template <typename T> T FloorExactSqrt(int c, T x){ T mn = 0; T mx = x; while(mx-mn > 1){ T ce = (mn+mx)/2; T nw = 1; for(int i = 0; c > i; i++){ if(x/ce < nw){ mx = ce; break; } nw *= ce; } if(mx != ce)mn = ce; } return mn; } struct MeisselLehmer{ long long N; long long alpha; SieveEratos sieve; BIT<int> varphiTable; struct d{ long long m,b; int cof; bool operator<(const d x)const{ if(m == x.m) return b < x.b; return m < x.m; } }; vector<d> varphiQueue; MeisselLehmer(long long n): N(n){ alpha = ceil(pow(N, 0.34)); sieve.set(N/alpha+10); } long long varphiLoop(long long n, long long a, int cof = 1){ if(a == 0){ return n; }else{ if(n/sieve.primes[a-1] <= N/alpha){ if(n/sieve.primes[a-1] >= 2){ varphiQueue.push_back({n/sieve.primes[a-1], a-1, cof*-1}); return varphiLoop(n, a-1, cof); }else{ return varphiLoop(n, a-1, cof) - varphiLoop(n/sieve.primes[a-1], a-1, cof*-1); } }else{ return varphiLoop(n, a-1, cof) - varphiLoop(n/sieve.primes[a-1], a-1, cof*-1); } } } long long varphi(long long n, long long a){ varphiTable.set(N/alpha+1); long long val = varphiLoop(n,a); sort(varphiQueue.begin(), varphiQueue.end()); int cur = 0; for(int i = 2; N/alpha >= i; i++){ varphiTable.add(sieve.invprimes[sieve.minp[i]], 1); while(cur < varphiQueue.size() && varphiQueue[cur].m == i){ val += varphiQueue[cur].cof * (varphiQueue[cur].m - varphiTable.query(1, varphiQueue[cur].b+1)); cur++; } } varphiQueue.clear(); return val; } long long P2(long long n, long long a){ long long val = 0; int cur = sieve.primes.size()-1; for(int i = a; n/sieve.primes[a-1] > sieve.primes[i]; i++){ while((sieve.primes[cur] > n / sieve.primes[i] || (n%sieve.primes[i] == 0 && sieve.primes[cur] == n/sieve.primes[i]))){ cur--; } if(cur < i)break; val += cur-i+1; } return val; } long long count(long long n = -1){ if(n == -1)n = N; long long prevN = N; N = n; alpha = ceil(pow(N, 0.34)); if(N < 2)return 0; else if(N < 3)return 1; long long val = varphi(N, alpha) + alpha-1 - P2(N, alpha); N = prevN; return val; } }; int main(){ long long L, R;cin>>L>>R; MeisselLehmer P(2LL*R); long long val = 0; if(L != R)val += P.count(2LL*R-1) - P.count(2LL*L); val += P.count(R) - P.count(L-1); cout << val << endl; return 0; }