fork download
copy 
  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.  
  11. int memo[1000100];
  12.  
  13. int mexer(unordered_set<int>&mex)
  14. {
  15.     int pr = 0;
  16.     while(mex.find(pr)!=mex.end())
  17.         pr++;
  18.     return pr;
  19. }
  20.  
  21. void getdivisors(int m, vector<int>&div)
  22. {
  23.     // div WILL HAVE ALL DIVISORS IN SORTED ORDER EXCEPT 1 AMD m
  24.     vector<int>sorted;
  25.     for(int i=2;i*i<=m;i++)
  26.     {
  27.         if(m%i==0)
  28.         {
  29.             if(i*i==m)
  30.                 div.PB(i);
  31.             else
  32.             {
  33.                 div.PB(i);
  34.                 sorted.PB(m/i);
  35.             }
  36.         }
  37.     }
  38.     int n = sorted.size();
  39.     for(int i=n-1;i>-1;i--)
  40.         div.PB(sorted[i]);
  41. }
  42.  
  43. void grundy(int m)
  44. {
  45.     if(memo[m]!=-1)
  46.         return;
  47.  
  48.     vector<int>div;
  49.     getdivisors(m,div);
  50.  
  51.     // PRIME NUBERS GRUNDY 0 AS NO REACHABLE STATE SO MEX(PHI) = 0
  52.     if(div.size()==0)
  53.     {
  54.         memo[m]=0;
  55.         return;
  56.     }
  57.  
  58.     unordered_set<int>mex;
  59.  
  60.     // INTO it PILES EACH OF SIZE m/it
  61.     for(auto it:div)
  62.     {
  63.  
  64.         // EVEN NUMBER OF XORS RESULTING IN 0
  65.         if(it%2==0)
  66.         {
  67.             mex.insert(0);
  68.         }
  69.         else
  70.         {
  71.             if(memo[m/it]==-1)
  72.                 grundy(m/it);
  73.             mex.insert(memo[m/it]);
  74.         }
  75.     }
  76.     memo[m] = mexer(mex);
  77. }
  78.  
  79. int main()
  80. {
  81.     ios::sync_with_stdio(0);
  82.     cin.tie(0);
  83. #ifndef ONLINE_JUDGE
  84.     freopen("input.txt", "r", stdin);
  85.     freopen("output.txt", "w", stdout);
  86. #endif
  87.  
  88.  
  89.     for(int i=0;i<1000100;i++)
  90.         memo[i] = -1;
  91.     memo[0] = 0;
  92.     memo[1] = 0;
  93.  
  94.     // for(int i=0;i<1000100;i++)
  95.     //     grundy(i);
  96.  
  97.     // for(int i=0;i<1000100;i++)
  98.     //     cout<<i<<": "<<memo[i]<<endl;
  99.  
  100.     int t,n,m;
  101.     cin>>t;
  102.     while(t--)
  103.     {
  104.         cin>>n;
  105.         int arr[n];
  106.         int res = 0;
  107.         for(int i=0;i<n;i++)
  108.         {
  109.             cin>>arr[i];
  110.             if(memo[arr[i]]==-1)
  111.                 grundy(arr[i]);
  112.             res ^= memo[arr[i]];
  113.         }
  114.         if(res==0)
  115.             cout<<2<<endl;
  116.         else
  117.             cout<<1<<endl;
  118.     }
  119.  
  120.  
  121.  
  122.     return 0;
  123.  
  124.  
  125. }
Success #stdin #stdout 0s 7420KB
comments (?)
stdin
copy 
2
2 
4 2
3 
5 2 3
stdout
copy 
1
2
https://ideone.com/dsLlUz
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!