fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int maxp = 1001;
  6. bool NotPrime[maxp];
  7. int prime[maxp];
  8. int cnt;
  9.  
  10. void sieve()
  11. {
  12.     NotPrime[0] = NotPrime[1] = 1;
  13.     for (int i = 2; i < maxp; i++) {
  14.         if (!NotPrime[i]) {
  15.             for (int j = i * i; j < maxp; j += i) {
  16.                 NotPrime[j] = 1;
  17.             }
  18.         }
  19.     }
  20.  
  21.     for (int i = 2; i < maxp; i++) {
  22.         if (!NotPrime[i]) prime[cnt++] = i;
  23.     }
  24. }
  25.  
  26. const int maxn = 1010, maxprime = 168;
  27. int n;
  28. int a[maxn];
  29. vector<bitset<maxprime> > S;
  30. int res;
  31.  
  32. int gauss(vector<bitset<maxprime> > a)
  33. {
  34.     int ans = 0;
  35.  
  36.     int n = (int)a.size();
  37.     int m = maxprime;
  38.  
  39.     for (int col = 0, row = 0; col < m && row < n; col++) {
  40.         for (int i = row; i < n; i++) {
  41.             if (a[i][col]) {
  42.                 swap(a[i], a[row]); 
  43.                 break;
  44.             }
  45.         }
  46.  
  47.         if (!a[row][col])
  48.             continue;
  49.  
  50.         ans++;
  51.  
  52.         for (int i = 0; i < n; i++) {
  53.             if (i != row && a[i][col]) {
  54.                 a[i] ^= a[row]; 
  55.             }
  56.         }
  57.         row++;
  58.     }
  59.  
  60.     return ans;
  61. }
  62.  
  63. void solve()
  64. {
  65.     sieve();
  66.     cin >> n;
  67.     for (int i = 1; i <= n; i++) {
  68.         cin >> a[i];
  69.         int x = a[i];
  70.         bitset<maxprime> tmp;
  71.         tmp.reset();
  72.         for (int p = 0; p < maxprime; p++) {
  73.             while (x % prime[p] == 0) {
  74.                 x /= prime[p];
  75.                 tmp.flip(p);
  76.             }
  77.         }
  78.         S.push_back(tmp);
  79.     }
  80.     cout << gauss(S);
  81. }
  82.  
  83. signed main()
  84. {
  85.     ios_base::sync_with_stdio(false);
  86.     cin.tie(0);
  87.  
  88.     solve();
  89. }
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/SfwHl6
language:
C++14 (clang 8.0)
created:
3 years 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!