fork download
copy 
  1. #define _USE_MATH_DEFINES
  2. #include <iostream>
  3. #include <cmath>
  4. #include <complex>
  5. #include <vector>
  6. #include <algorithm>
  7. #include <string>
  8.  
  9. using namespace std;
  10.  
  11. #define sz(v) ((int)(v).size())
  12. #define all(v) (v).begin(),(v).end()
  13. typedef complex<double> base;
  14. using ll = long long;
  15.  
  16. void fft(vector <base>& a, bool invert)
  17. {
  18. 	int n = sz(a);
  19. 	for (int i = 1, j = 0; i < n; i++) {
  20. 		int bit = n >> 1;
  21. 		for (; j >= bit; bit >>= 1) j -= bit;
  22. 		j += bit;
  23. 		if (i < j) swap(a[i], a[j]);
  24. 	}
  25. 	for (int len = 2; len <= n; len <<= 1) {
  26. 		double ang = 2 * M_PI / len * (invert ? -1 : 1);
  27. 		base wlen(cos(ang), sin(ang));
  28. 		for (int i = 0; i < n; i += len) {
  29. 			base w(1);
  30. 			for (int j = 0; j < len / 2; j++) {
  31. 				base u = a[i + j], v = a[i + j + len / 2] * w;
  32. 				a[i + j] = u + v;
  33. 				a[i + j + len / 2] = u - v;
  34. 				w *= wlen;
  35. 			}
  36. 		}
  37. 	}
  38. 	if (invert) {
  39. 		for (int i = 0; i < n; i++) a[i] /= n;
  40. 	}
  41. }
  42.  
  43. void multiply(const vector<ll>& a, const vector<ll >& b, vector<ll>& res)
  44. {
  45. 	vector <base> fa(all(a)), fb(all(b));
  46. 	int n = 1;
  47. 	while (n < max(sz(a), sz(b))) n <<= 1;
  48. 	n <<= 1;
  49. 	fa.resize(n); fb.resize(n);
  50. 	fft(fa, false); fft(fb, false);
  51. 	for (int i = 0; i < n; i++) fa[i] *= fb[i];
  52. 	fft(fa, true);
  53. 	res.resize(n);
  54. 	for (int i = 0; i < n; i++) res[i] = int(fa[i].real() + (fa[i].real() > 0 ? 0.5 : -0.5));
  55. }
  56.  
  57. const ll n_ = 1001010;
  58. ll p[n_], a, b, c, x, y, n;
  59. int main() {
  60. 	ios_base::sync_with_stdio(0);
  61. 	cin.tie(0), cout.tie(0);
  62. 	vector<ll>A(n_), B(n_), C;
  63. 	for (int i = 2; i < n_; i++)
  64. 		if (p[i])continue;
  65. 		else {
  66. 			A[i] = 1;
  67. 			B[i] = 1;
  68. 			for (int j = i + i; j < n_; j += i)p[j] = 1;
  69. 		}
  70. 	cin >> n;
  71. 	multiply(A, B, C);
  72. 	for (int i = 0; i < n; i++) {
  73. 		cin >> a;
  74. 		b = C[a];
  75. 		if (!p[a / 2])b++;
  76. 		b /= 2;
  77. 		cout << b << '\n';
  78. 	}
  79. }
  80.  
  81.  
Success #stdin #stdout 0.89s 109000KB
comments (?)
stdin
copy 
5
6
8
10
12
100
stdout
copy 
1
1
2
1
6
https://ideone.com/BtXsx1
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!