fork download
copy 
  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 "divgroup"
  8. #define endl '\n'
  9. #define F first
  10. #define S second
  11. #define all(v) (v).begin(), (v).end()
  12. #define TIME (1.0 * clock() / CLOCKS_PER_SEC)
  13. #define ll long long
  14. #define log2(x) 63 - __builtin_clzll(x)
  15. #define FOR(i, l, r) for(int i = (l), _r = (r); i <= _r; ++i)
  16. #define FORD(i, l, r) for(int i = (l), _r = (r); i >= _r; --i)
  17.  
  18. using namespace std;
  19. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  20. int rnd(int l, int r)
  21. {
  22.     return l + rng() % (r - l + 1);
  23. }
  24.  
  25. int const LIM = 1e7 + 7;
  26. int const N = 1e6 + 6;
  27. int n, a[N], par[LIM], ans, pos[LIM];
  28.  
  29. int Find(int u)
  30. {
  31.     return par[u] == u ? u : par[u] = Find(par[u]);
  32. }
  33.  
  34. void Union(int u, int v)
  35. {
  36.     u = Find(u), v = Find(v);
  37.     if (u == v) return;
  38.     --ans;
  39.     par[v] = u;
  40. }
  41.  
  42. /**
  43.  
  44. (x^2 - y^2, 2xy, x2 + y2)
  45. (x^2 - y^2) ^ 2 + (2xy)^2 = (x^2 + y^2) ^ 2
  46.  
  47. 2 * x * y <= 1e7 -> y <= sqrt(1e7 / 2)
  48.  
  49. **/
  50.  
  51. void Process()
  52. {
  53.     ans = n;
  54.     for (ll x = 1; x <= 1e7; ++x)
  55.         for (ll y = 1; y < x and 2 * x * y <= 1e7; y++)
  56.         {
  57.             ll a = x * x - y * y;
  58.             ll b = 2 * x * y;
  59.             ll c = x * x + y * y;
  60.  
  61.             if (a <= 1e7 and __gcd(a, b) == 1)
  62.             {
  63.                 if (pos[a] != 0 and pos[b] != 0) Union(pos[a], pos[b]);
  64.                 if (c <= 1e7)
  65.                 {
  66.                     if (pos[b] != 0 and pos[c] != 0) Union(pos[b], pos[c]);
  67.                     if (pos[a] != 0 and pos[c] != 0) Union(pos[c], pos[a]);
  68.                 }
  69.             }
  70.         }
  71.     cout << ans;
  72. }
  73.  
  74. void Gen(void)
  75. {
  76.     int n = rnd(3, 30);
  77.     cout << n << '\n';
  78.     for (int i = 1; i <= n; ++i) cout << rnd(5, 1e7) << ' ';
  79. }
  80.  
  81. signed main()
  82. {
  83.     cin.tie(NULL)->sync_with_stdio(false);
  84.     if (fopen(task".inp", "r"))
  85.     {
  86.         freopen(task".inp", "r", stdin);
  87.         freopen(task".out", "w", stdout);
  88.     }
  89.  
  90.     cin >> n;
  91.     for (int i = 1; i <= n; ++i)
  92.         cin >> a[i], pos[a[i]] = i, par[i] = i;
  93.     Process();
  94.  
  95.     ///Gen();
  96.  
  97.     cerr << '\n' << "Time collapsed: " << TIME << '\n';
  98.  
  99.     return 0;
  100. }
Success #stdin #stdout #stderr 0.85s 5756KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Time collapsed: 0.848895
https://ideone.com/uya5La
language:
C++14 (gcc 8.3)
created:
3 days 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!