firiexp's Library
This documentation is automatically generated by online-judge-tools/verification-helper
test/yosupo_enumerate_primes_get_prime_wheel.test.cpp
- View this file on GitHub
- Last update: 2026-03-22 19:39:35+09:00
- Problem: https://judge.yosupo.jp/problem/enumerate_primes
Depends on
Code
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_primes"
#include <algorithm>
#include <cmath>
#include <vector>
#include <array>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#include <cstdio>
#include <cstring>
#include <string>
#include <type_traits>
#include "../util/fastio.cpp"
#include "../math/prime/get_prime_wheel.cpp"
int main() {
Scanner sc;
Printer pr;
int n, a, b;
sc.read(n, a, b);
Prime prime(n, a, b);
pr.print(prime.count);
pr.print(' ');
pr.println((prime.count <= b ? 0 : (prime.count - b + a - 1) / a));
pr.println(prime.picked);
}#line 1 "test/yosupo_enumerate_primes_get_prime_wheel.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_primes"
#include <algorithm>
#include <cmath>
#include <vector>
#include <array>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#include <cstdio>
#include <cstring>
#include <string>
#include <type_traits>
#line 1 "util/fastio.cpp"
using namespace std;
extern "C" int fileno(FILE *);
extern "C" int isatty(int);
template<class T, class = void>
struct is_fastio_range : false_type {};
template<class T>
struct is_fastio_range<T, void_t<decltype(declval<T &>().begin()), decltype(declval<T &>().end())>> : true_type {};
template<class T, class = void>
struct has_fastio_value : false_type {};
template<class T>
struct has_fastio_value<T, void_t<decltype(declval<const T &>().value())>> : true_type {};
struct FastIoDigitTable {
char num[40000];
constexpr FastIoDigitTable() : num() {
for (int i = 0; i < 10000; ++i) {
int x = i;
for (int j = 3; j >= 0; --j) {
num[i * 4 + j] = char('0' + x % 10);
x /= 10;
}
}
}
};
struct Scanner {
static constexpr int BUFSIZE = 1 << 17;
static constexpr int OFFSET = 64;
char buf[BUFSIZE + 1];
int idx, size;
bool interactive;
Scanner() : idx(0), size(0), interactive(isatty(fileno(stdin))) {}
inline void load() {
int len = size - idx;
memmove(buf, buf + idx, len);
if (interactive) {
if (fgets(buf + len, BUFSIZE + 1 - len, stdin)) size = len + (int)strlen(buf + len);
else size = len;
} else {
size = len + (int)fread(buf + len, 1, BUFSIZE - len, stdin);
}
idx = 0;
buf[size] = 0;
}
inline void ensure() {
if (idx + OFFSET > size) load();
}
inline void ensure_interactive() {
if (idx == size) load();
}
inline char skip() {
if (interactive) {
ensure_interactive();
while (buf[idx] && buf[idx] <= ' ') {
++idx;
ensure_interactive();
}
return buf[idx++];
}
ensure();
while (buf[idx] && buf[idx] <= ' ') {
++idx;
ensure();
}
return buf[idx++];
}
template<class T, typename enable_if<is_integral<T>::value, int>::type = 0>
void read(T &x) {
if (interactive) {
char c = skip();
bool neg = false;
if constexpr (is_signed<T>::value) {
if (c == '-') {
neg = true;
ensure_interactive();
c = buf[idx++];
}
}
x = 0;
while (c >= '0') {
x = x * 10 + (c & 15);
ensure_interactive();
c = buf[idx++];
}
if constexpr (is_signed<T>::value) {
if (neg) x = -x;
}
return;
}
char c = skip();
bool neg = false;
if constexpr (is_signed<T>::value) {
if (c == '-') {
neg = true;
c = buf[idx++];
}
}
x = 0;
while (c >= '0') {
x = x * 10 + (c & 15);
c = buf[idx++];
}
if constexpr (is_signed<T>::value) {
if (neg) x = -x;
}
}
template<class T, typename enable_if<!is_integral<T>::value && !is_fastio_range<T>::value && !is_same<typename decay<T>::type, string>::value && has_fastio_value<T>::value, int>::type = 0>
void read(T &x) {
long long v;
read(v);
x = T(v);
}
template<class Head, class Next, class... Tail>
void read(Head &head, Next &next, Tail &...tail) {
read(head);
read(next, tail...);
}
template<class T, class U>
void read(pair<T, U> &p) {
read(p.first, p.second);
}
template<class T, typename enable_if<is_fastio_range<T>::value && !is_same<typename decay<T>::type, string>::value, int>::type = 0>
void read(T &a) {
for (auto &x : a) read(x);
}
void read(char &c) {
c = skip();
}
void read(string &s) {
s.clear();
if (interactive) {
ensure_interactive();
while (buf[idx] && buf[idx] <= ' ') {
++idx;
ensure_interactive();
}
while (true) {
int start = idx;
while (idx < size && buf[idx] > ' ') ++idx;
s.append(buf + start, idx - start);
if (idx < size) break;
load();
if (size == 0) break;
}
if (idx < size) ++idx;
return;
}
ensure();
while (buf[idx] && buf[idx] <= ' ') {
++idx;
ensure();
}
while (true) {
int start = idx;
while (idx < size && buf[idx] > ' ') ++idx;
s.append(buf + start, idx - start);
if (idx < size) break;
load();
}
if (idx < size) ++idx;
}
};
struct Printer {
static constexpr int BUFSIZE = 1 << 17;
static constexpr int OFFSET = 64;
char buf[BUFSIZE];
int idx;
bool interactive;
inline static constexpr FastIoDigitTable table{};
Printer() : idx(0), interactive(isatty(fileno(stdout))) {}
~Printer() { flush(); }
inline void flush() {
if (idx) {
fwrite(buf, 1, idx, stdout);
idx = 0;
}
}
inline void pc(char c) {
if (idx > BUFSIZE - OFFSET) flush();
buf[idx++] = c;
if (interactive && c == '\n') flush();
}
inline void print_range(const char *s, size_t n) {
size_t pos = 0;
while (pos < n) {
if (idx == BUFSIZE) flush();
size_t chunk = min(n - pos, (size_t)(BUFSIZE - idx));
memcpy(buf + idx, s + pos, chunk);
idx += (int)chunk;
pos += chunk;
}
}
void print(const char *s) {
print_range(s, strlen(s));
}
void print(const string &s) {
print_range(s.data(), s.size());
}
void print(char c) {
pc(c);
}
void print(bool b) {
pc(char('0' + (b ? 1 : 0)));
}
template<class T, typename enable_if<is_integral<T>::value && !is_same<T, bool>::value, int>::type = 0>
void print(T x) {
if (idx > BUFSIZE - 100) flush();
using U = typename make_unsigned<T>::type;
U y;
if constexpr (is_signed<T>::value) {
if (x < 0) {
buf[idx++] = '-';
y = U(0) - static_cast<U>(x);
} else {
y = static_cast<U>(x);
}
} else {
y = x;
}
if (y == 0) {
buf[idx++] = '0';
return;
}
static constexpr int TMP_SIZE = sizeof(U) * 10 / 4;
char tmp[TMP_SIZE];
int pos = TMP_SIZE;
while (y >= 10000) {
pos -= 4;
memcpy(tmp + pos, table.num + (y % 10000) * 4, 4);
y /= 10000;
}
if (y >= 1000) {
memcpy(buf + idx, table.num + (y << 2), 4);
idx += 4;
} else if (y >= 100) {
memcpy(buf + idx, table.num + (y << 2) + 1, 3);
idx += 3;
} else if (y >= 10) {
unsigned q = (unsigned(y) * 205) >> 11;
buf[idx] = char('0' + q);
buf[idx + 1] = char('0' + (unsigned(y) - q * 10));
idx += 2;
} else {
buf[idx++] = char('0' + y);
}
memcpy(buf + idx, tmp + pos, TMP_SIZE - pos);
idx += TMP_SIZE - pos;
}
template<class T, typename enable_if<!is_integral<T>::value && !is_fastio_range<T>::value && !is_same<typename decay<T>::type, string>::value && has_fastio_value<T>::value, int>::type = 0>
void print(const T &x) {
print(x.value());
}
template<class T, typename enable_if<is_fastio_range<T>::value && !is_same<typename decay<T>::type, string>::value, int>::type = 0>
void print(const T &a) {
bool first = true;
for (auto &&x : a) {
if (!first) pc(' ');
first = false;
print(x);
}
}
template<class T>
void println(const T &x) {
print(x);
pc('\n');
}
template<class Head, class... Tail>
void println(const Head &head, const Tail &...tail) {
print(head);
((pc(' '), print(tail)), ...);
pc('\n');
}
void println() {
pc('\n');
}
};
template<class T>
Scanner &operator>>(Scanner &in, T &x) {
in.read(x);
return in;
}
template<class T>
Printer &operator<<(Printer &out, const T &x) {
out.print(x);
return out;
}
/**
* @brief 高速入出力(Fast IO)
*/
#line 1 "math/prime/get_prime_wheel.cpp"
struct Prime {
static constexpr int wheel[8] = {4, 2, 4, 2, 4, 6, 2, 6};
static constexpr int wheel2[8] = {7, 11, 13, 17, 19, 23, 29, 31};
static constexpr int wheel_sum[30] = {
0, 0, 0, 0, 0, 0, 1, 1, 1, 1,
2, 2, 3, 3, 3, 3, 4, 4, 5, 5,
5, 5, 6, 6, 6, 6, 6, 6, 7, 7
};
static constexpr int off64[64] = {
0, 4, 6, 10, 12, 16, 22, 24,
30, 34, 36, 40, 42, 46, 52, 54,
60, 64, 66, 70, 72, 76, 82, 84,
90, 94, 96,100,102,106,112,114,
120,124,126,130,132,136,142,144,
150,154,156,160,162,166,172,174,
180,184,186,190,192,196,202,204,
210,214,216,220,222,226,232,234
};
// old 1-based
static inline int f(int n) { return (n - 1) / 30 * 8 + wheel_sum[(n - 1) % 30]; }
static inline int g(int n) { return ((n - 1) >> 3) * 30 + wheel2[(n - 1) & 7]; }
// internal 0-based
static inline int f0(int n) { return f(n) - 1; }
static inline int g0(int n) { return (n >> 3) * 30 + wheel2[n & 7]; }
int count = 0;
vector<int> primes;
vector<int> picked;
private:
static void build_sieve(int M, vector<ull>& sieve, int& n0) {
if (M < 7) {
n0 = -1;
sieve.clear();
return;
}
n0 = f0(M);
int sq = (int)std::sqrt((double)M);
int k0 = (sq >= 7 ? f0(sq) : -1);
int num = n0 + 1;
sieve.assign((num + 63) >> 6, ~0ULL);
if (num & 63) sieve.back() &= (1ULL << (num & 63)) - 1;
auto* sv = sieve.data();
array<int, 8> delta{};
for (int i = 0; i <= k0; ++i) {
if (((sv[i >> 6] >> (i & 63)) & 1ULL) == 0) continue;
int p = g0(i);
int phase0 = i & 7;
long long cur = 1LL * p * p;
int idx = f0((int)cur);
for (int t = 0; t < 8; ++t) {
long long nxt = cur + 1LL * wheel[(phase0 + t) & 7] * p;
delta[t] = f((int)nxt) - f((int)cur);
cur = nxt;
}
const int d0 = delta[0];
const int d1 = delta[1];
const int d2 = delta[2];
const int d3 = delta[3];
const int d4 = delta[4];
const int d5 = delta[5];
const int d6 = delta[6];
const int d7 = delta[7];
while (idx <= n0) {
sv[idx >> 6] &= ~(1ULL << (idx & 63));
idx += d0;
if (idx > n0) break;
sv[idx >> 6] &= ~(1ULL << (idx & 63));
idx += d1;
if (idx > n0) break;
sv[idx >> 6] &= ~(1ULL << (idx & 63));
idx += d2;
if (idx > n0) break;
sv[idx >> 6] &= ~(1ULL << (idx & 63));
idx += d3;
if (idx > n0) break;
sv[idx >> 6] &= ~(1ULL << (idx & 63));
idx += d4;
if (idx > n0) break;
sv[idx >> 6] &= ~(1ULL << (idx & 63));
idx += d5;
if (idx > n0) break;
sv[idx >> 6] &= ~(1ULL << (idx & 63));
idx += d6;
if (idx > n0) break;
sv[idx >> 6] &= ~(1ULL << (idx & 63));
idx += d7;
}
}
}
public:
Prime(int M) {
if (M >= 17) {
primes.reserve(max(0, (int)(M / (log((double)M) - 1.12))));
}
if (M >= 2) primes.push_back(2), ++count;
if (M >= 3) primes.push_back(3), ++count;
if (M >= 5) primes.push_back(5), ++count;
if (M < 7) return;
vector<ull> sieve;
int n0;
build_sieve(M, sieve, n0);
int words = (n0 + 64) >> 6;
for (int w = 0; w < words; ++w) {
ull bits = sieve[w];
int base = 240 * w + 7; // 64 candidates = 8 cycles = 240 numbers
while (bits) {
int t = __builtin_ctzll(bits);
primes.push_back(base + off64[t]);
++count;
bits &= bits - 1;
}
}
}
Prime(int M, int a, int b) {
int next_pick = b;
auto add_small = [&](int p) {
if (count == next_pick) {
picked.push_back(p);
next_pick += a;
}
++count;
};
if (M >= 2) add_small(2);
if (M >= 3) add_small(3);
if (M >= 5) add_small(5);
if (M < 7) return;
vector<ull> sieve;
int n0;
build_sieve(M, sieve, n0);
int words = (n0 + 64) >> 6;
for (int w = 0; w < words; ++w) {
ull bits = sieve[w];
int pc = __builtin_popcountll(bits);
if (next_pick >= count + pc) {
count += pc;
continue;
}
int base = 240 * w + 7;
while (bits) {
int t = __builtin_ctzll(bits);
if (count == next_pick) {
picked.push_back(base + off64[t]);
next_pick += a;
}
++count;
bits &= bits - 1;
}
}
}
};
constexpr int Prime::wheel[8];
constexpr int Prime::wheel2[8];
constexpr int Prime::wheel_sum[30];
constexpr int Prime::off64[64];
#line 18 "test/yosupo_enumerate_primes_get_prime_wheel.test.cpp"
int main() {
Scanner sc;
Printer pr;
int n, a, b;
sc.read(n, a, b);
Prime prime(n, a, b);
pr.print(prime.count);
pr.print(' ');
pr.println((prime.count <= b ? 0 : (prime.count - b + a - 1) / a));
pr.println(prime.picked);
}