結果
問題 | No.1661 Sum is Prime (Hard Version) |
ユーザー |
👑 ![]() |
提出日時 | 2021-08-27 21:51:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 408 ms / 3,000 ms |
コード長 | 3,571 bytes |
コンパイル時間 | 2,476 ms |
コンパイル使用メモリ | 200,504 KB |
最終ジャッジ日時 | 2025-01-24 02:53:52 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
#define _USE_MATH_DEFINES#include <bits/stdc++.h>using namespace std;#define FOR(i,m,n) for(int i=(m);i<(n);++i)#define REP(i,n) FOR(i,0,n)#define ALL(v) (v).begin(),(v).end()using ll = long long;constexpr int INF = 0x3f3f3f3f;constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;constexpr double EPS = 1e-8;constexpr int MOD = 1000000007;// constexpr int MOD = 998244353;constexpr int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};constexpr int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }struct IOSetup {IOSetup() {std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false);std::cout << fixed << setprecision(20);}} iosetup;// https://github.com/ei1333/library/blob/e4888de51cc691c32057e308cb8a5beb05e78f7b/math/number-theory/kth-root-integer.cppuint64_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;}// https://github.com/ei1333/library/blob/e4888de51cc691c32057e308cb8a5beb05e78f7b/math/number-theory/prime-table.cppvector< 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;}// https://github.com/ei1333/library/blob/e4888de51cc691c32057e308cb8a5beb05e78f7b/math/number-theory/prime-count.cpptemplate< 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);}};int main() {ll l, r; cin >> l >> r;PrimeCount prime_count;ll ans = prime_count.pi(r) - prime_count.pi(l - 1);if (l < r) ans += prime_count.pi(2 * (r - 1) + 1) - prime_count.pi(2 * l);cout << ans << '\n';return 0;}