#include #include #include #include #include #include #include using namespace std; using cplx = complex; void fft(vector &coeffs) { constexpr auto _2_pi = 2.0 * numbers::pi_v; int n = coeffs.size(); int j = 0; for (int i = 1; i < n; i++) { int bit = n >> 1; while (j >= bit) { j -= bit; bit >>= 1; } j += bit; if (i < j) { swap(coeffs[i], coeffs[j]); } } double angle = -_2_pi / n; vector roots(n / 2); for (int i = 0; i < n / 2; i++) { roots[i] = exp(cplx(0, angle * i)); } for (int len = 2; len <= n; len <<= 1) { int step = n / len; for (int i = 0; i < n; i += len) { for (int j = 0; j < len / 2; j++) { cplx u = coeffs[i + j], v = coeffs[i + j + len / 2] * roots[step * j]; coeffs[i + j] = u + v; coeffs[i + j + len / 2] = u - v; } } } } void ifft(vector &coeffs) { constexpr auto _2_pi = 2.0 * numbers::pi_v; int n = coeffs.size(); int j = 0; for (int i = 1; i < n; i++) { int bit = n >> 1; while (j >= bit) { j -= bit; bit >>= 1; } j += bit; if (i < j) { swap(coeffs[i], coeffs[j]); } } double angle = _2_pi / n; vector roots(n / 2); for (int i = 0; i < n / 2; i++) { roots[i] = exp(cplx(0, angle * i)); } for (int len = 2; len <= n; len <<= 1) { int step = n / len; for (int i = 0; i < n; i += len) { for (int j = 0; j < len / 2; j++) { cplx u = coeffs[i + j], v = coeffs[i + j + len / 2] * roots[step * j]; coeffs[i + j] = u + v; coeffs[i + j + len / 2] = u - v; } } } for (int i = 0; i < n; i++) { coeffs[i] /= n; } } vector multiply(vector &a, vector &b) { vector fa(a.begin(), a.end()), fb(b.begin(), b.end()); int n = 2; while (n < a.size() + b.size()) { n <<= 1; } fa.resize(n); fb.resize(n); fft(fa); fft(fb); for (int i = 0; i < n; i++) { fa[i] *= fb[i]; } ifft(fa); vector result; for (int i = 0; i < n; i++) { result.push_back(round(fa[i].real())); } return result; } int main() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); vector primes; vector visited(1000001, 0); for (int i = 2; i <= 1000000; i++) { if (!visited[i]) { primes.push_back(i); for (int j = 2 * i; j <= 1000000; j += i) { visited[j] = 1; } } } vector v(500001, 0); for (int i : primes) { if (i == 2) { continue; } v[(i - 1) / 2] = 1; } vector result = multiply(v, v); int x; cin >> x; while (x--) { int k; cin >> k; if (k == 4) { cout << "1\n"; continue; } cout << result[k / 2 - 1] / 2 + result[k / 2 - 1] % 2 << '\n'; } return 0; }

코드 #5408