fork(1) download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define PB push_back
  5. #define FI first
  6. #define SE second
  7. #define MP make_pair
  8. #define ALL(cont) cont.begin(), cont.end()
  9. #define MOD 1000000007ll
  10. #define SIZE 100100ll
  11.  
  12. vector<ll>divisors[SIZE];
  13.  
  14. void divisorscalc()
  15. {
  16.     for (ll i = 2; i < SIZE; i++)
  17.     {
  18.         for (ll j = i; j < SIZE; j += i)
  19.             divisors[j].PB(i);
  20.     }
  21. }
  22.  
  23. ll mexer(unordered_set<ll>&s)
  24. {
  25.     ll x = 0;
  26.     while (s.find(x) != s.end())
  27.         x++;
  28.     return x;
  29. }
  30.  
  31. ll memo[SIZE];
  32. void grundy(ll m)
  33. {
  34.     if (memo[m] != -1)
  35.         return;
  36.     unordered_set<ll>mex;
  37.     for (auto it : divisors[m])
  38.     {
  39.         if (memo[m / it] == -1)
  40.             grundy(m / it);
  41.         if (it % 2 == 0)
  42.             mex.insert(0);
  43.         else
  44.             mex.insert(memo[m / it]);
  45.     }
  46.     memo[m] = mexer(mex);
  47. }
  48.  
  49.  
  50. int main()
  51. {
  52.     ios::sync_with_stdio(0);
  53.     cin.tie(0); cout.tie(0);
  54. #ifndef ONLINE_JUDGE
  55.     freopen("input.txt", "r", stdin);
  56.     freopen("output.txt", "w", stdout);
  57. #endif
  58.  
  59.  
  60.  
  61.  
  62.     divisorscalc();
  63.     for (ll i = 0; i < SIZE; i++)
  64.         memo[i] = -1;
  65.     memo[0] = 0;
  66.     memo[1] = 0;
  67.     for (ll i = 2; i < SIZE; i++)
  68.     {
  69.         if (memo[i] == -1)
  70.             grundy(i);
  71.     }
  72.  
  73.     int t, n, m;
  74.     cin >> t;
  75.     while (t--)
  76.     {
  77.         cin >> n;
  78.         int arr[n];
  79.         int res = 0;
  80.         for (int i = 0; i < n; i++)
  81.         {
  82.             cin >> arr[i];
  83.             res ^= memo[arr[i]];
  84.         }
  85.         if (res == 0)
  86.             cout << 2 << endl;
  87.         else
  88.             cout << 1 << endl;
  89.     }
  90.  
  91.  
  92.  
  93.     return 0;
  94.  
  95.  
  96. }
Success #stdin #stdout 0.12s 19564KB
comments (?)
stdin 
2
2 
4 2
3 
5 2 3
stdout 
2
1
https://ideone.com/WKy105
language:
C++14 (gcc 8.3)
created:
5 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!