結果
問題 |
No.1661 Sum is Prime (Hard Version)
|
ユーザー |
|
提出日時 | 2021-08-27 21:38:29 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,293 bytes |
コンパイル時間 | 596 ms |
コンパイル使用メモリ | 57,700 KB |
最終ジャッジ日時 | 2025-03-23 12:33:39 |
合計ジャッジ時間 | 1,290 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp:4:1: error: ‘uint64_t’ does not name a type 4 | uint64_t kth_root_integer(uint64_t a, int k) { | ^~~~~~~~ main.cpp:3:1: note: ‘uint64_t’ is defined in header ‘<cstdint>’; did you forget to ‘#include <cstdint>’? 2 | #include<vector> +++ |+#include <cstdint> 3 | using namespace std; main.cpp: In member function ‘int64_t PrimeCount<LIM>::p2(int64_t, int64_t)’: main.cpp:41:20: error: there are no arguments to ‘kth_root_integer’ that depend on a template parameter, so a declaration of ‘kth_root_integer’ must be available [-fpermissive] 41 | int64_t b = pi(kth_root_integer(x, 2)); | ^~~~~~~~~~~~~~~~ main.cpp:41:20: note: (if you use ‘-fpermissive’, G++ will accept your code, but allowing the use of an undeclared name is deprecated) main.cpp: In member function ‘int64_t PrimeCount<LIM>::phi(int64_t, int64_t)’: main.cpp:54:23: error: there are no arguments to ‘kth_root_integer’ that depend on a template parameter, so a declaration of ‘kth_root_integer’ must be available [-fpermissive] 54 | int64_t sx = pi(kth_root_integer(m, 2)); | ^~~~~~~~~~~~~~~~ main.cpp: In constructor ‘PrimeCount<LIM>::PrimeCount()’: main.cpp:64:21: error: there are no arguments to ‘kth_root_integer’ that depend on a template parameter, so a declaration of ‘kth_root_integer’ must be available [-fpermissive] 64 | PrimeCount() : sq(kth_root_integer(LIM, 2)), prime_sum(sq + 1) { | ^~~~~~~~~~~~~~~~ main.cpp: In member function ‘int64_t PrimeCount<LIM>::pi(int64_t)’: main.cpp:73:17: error: there are no arguments to ‘kth_root_integer’ that depend on a template parameter, so a declaration of ‘kth_root_integer’ must be available [-fpermissive] 73 | int64_t m = kth_root_integer(n, 3); | ^~~~~~~~~~~~~~~~ main.cpp: At global scope: main.cpp:79:1: warning: ISO C++ forbids declaration of ‘ma
ソースコード
#include<iostream> #include<vector> using namespace std; uint64_t kth_root_integer(uint64_t a, int k) { if(k == 1) return a; auto check = [&](uint32_t x) { uint64_t mul = 1; for(int j = 0; j < k; j++) { if(__builtin_mul_overflow(mul, x, &mul)) return false; } return mul <= a; }; uint64_t ret = 0; for(int i = 31; i >= 0; i--) { if(check(ret | (1u << i))) ret |= 1u << i; } return ret; } vector< bool > prime_table(int n) { vector< bool > prime(n + 1, true); if(n >= 0) prime[0] = false; if(n >= 1) prime[1] = false; for(int i = 2; i * i <= n; i++) { if(!prime[i]) continue; for(int j = i * i; j <= n; j += i) { prime[j] = false; } } return prime; } template< int64_t LIM = 100000000000LL > struct PrimeCount { private: int64_t sq; vector< bool > prime; vector< int64_t > prime_sum, primes; int64_t p2(int64_t x, int64_t y) { if(x < 4) return 0; int64_t a = pi(y); int64_t b = pi(kth_root_integer(x, 2)); if(a >= b) return 0; int64_t sum = (a - 2) * (a + 1) / 2 - (b - 2) * (b + 1) / 2; for(int64_t i = a; i < b; i++) sum += pi(x / primes[i]); return sum; } int64_t phi(int64_t m, int64_t n) { if(m < 1) return 0; if(n > m) return 1; if(n < 1) return m; if(m <= primes[n - 1] * primes[n - 1]) return pi(m) - n + 1; if(m <= primes[n - 1] * primes[n - 1] * primes[n - 1] && m <= sq) { int64_t sx = pi(kth_root_integer(m, 2)); int64_t ans = pi(m) - (sx + n - 2) * (sx - n + 1) / 2; for(int64_t i = n; i < sx; ++i) ans += pi(m / primes[i]); return ans; } return phi(m, n - 1) - phi(m / primes[n - 1], n - 1); } public: PrimeCount() : sq(kth_root_integer(LIM, 2)), prime_sum(sq + 1) { prime = prime_table(sq); for(int i = 1; i <= sq; i++) prime_sum[i] = prime_sum[i - 1] + prime[i]; primes.reserve(prime_sum[sq]); for(int i = 1; i <= sq; i++) if(prime[i]) primes.push_back(i); } int64_t pi(int64_t n) { if(n <= sq) return prime_sum[n]; int64_t m = kth_root_integer(n, 3); int64_t a = pi(m); return phi(n, a) + a - 1 - p2(n, m); } }; long L,R; main() { PrimeCount<>Q; cin>>L>>R; long ans=Q.pi(R)-Q.pi(L-1); ans+=Q.pi(2*R-1); ans-=Q.pi(2*L-1); if(L==1&&R>=2)ans--; cout<<ans<<endl; }