fork download 
  1. #include <bits/stdc++.h>
  2. #define BIT(x, i) (1 & ((x) >> (i)))
  3. #define MASK(x) (1LL << (x))
  4. #define OFF(x, i) ((x) & ~(1LL << (i)))
  5. #define ON(x, i) ((1LL << (i)) | (x))
  6. #define CNT(x) __builtin_popcountll(x)
  7. #define task""
  8. #define freopen freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout);
  9. #define endl '\n'
  10. #define F first
  11. #define S second
  12. #define TIME (1.0 * clock() / CLOCKS_PER_SEC)
  13.  
  14. using namespace std;
  15. int t, n;
  16. int const N = 2e6 + 6;
  17. int p[N], pre[N];
  18.  
  19. void Sieve()
  20. {
  21.     memset(p, 0, sizeof p);
  22.     p[1] = 1;
  23.     for (int i = 2; i * i <= N; i++)
  24.     {
  25.         if (p[i] == 0)
  26.             for (int j = i * i; j <= N; j += i)
  27.                 p[j] = 1;
  28.     }
  29. }
  30.  
  31. void Prefix()
  32. {
  33.     pre[0] = 0;
  34.     for (int i = 1; i <= N; i++)
  35.     {
  36.         if (!p[i]) pre[i] = pre[i - 1] + 1;
  37.         else pre[i] = pre[i - 1];
  38.     }
  39. }
  40.  
  41. void Sub1()
  42. {
  43.     int cnt = 0, t1 = 0, t2 = 0, sum = 0;
  44.         for (int i = 1; i <= n - 2; i++)
  45.         {
  46.             for (int j = i + 1; j <= n - 1; j++)
  47.                 for (int k = j + 1; k <= n; k++)
  48.             {
  49.                 if ((!p[i + j] && !p[j + k] && !p[i + k]) || (p[i + j] && p[i + k] && p[j + k])) cnt++;
  50.             }
  51.         }
  52.         cout << cnt << endl;
  53. }
  54.  
  55. void Sub2()
  56. {
  57.     vector <int> x(n + 1, 0), y(n + 1, 0);
  58.     for (int i = 1; i < n; i++)
  59.         for (int j = i + 1; j <= n; j++)
  60.     {
  61.         if (p[i + j]) x[i]++, x[j]++;
  62.         else y[i]++, y[j]++;
  63.     }
  64.  
  65.     long long diff = 0;
  66.     for (int i = 1; i <= n; i++) diff += 1LL * x[i] * y[i];
  67.     diff /= 2;
  68.     long long total = 1LL * n * (n - 1) * (n - 2)/6;
  69.     cout << total - diff << endl;
  70. }
  71.  
  72. void Sub3()
  73. {
  74.     long long diff = 0;
  75.     for (int i = 1; i < n; i++)
  76.     {
  77.         int x = pre[i + n] - pre[i];
  78.         int y = n - x - 1;
  79.         diff += 1LL * x * y;
  80.     }
  81.     diff /= 2;
  82.     long long total = 1LL * n * (n - 1) * (n - 2)/6;
  83.     cout << total - diff << endl;
  84. }
  85.  
  86. int main()
  87. {
  88.     ios_base::sync_with_stdio(false);
  89.     cin.tie(0);
  90.     cout.tie(0);
  91.     //freopen
  92.  
  93.     Sieve();
  94.     Prefix();
  95.     cin >> t;
  96.     while (t--)
  97.     {
  98.         cin >> n;
  99.         Sub2();
  100.     }
  101.  
  102.     cerr << endl << TIME << endl;
  103.     return 0;
  104. }
  105.  
Success #stdin #stdout #stderr 0.02s 19372KB
comments (?)
stdin 
2
3
5
stdout 
0
1
stderr 
0.018678
https://ideone.com/8jKHVx
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!