fork download
copy 
  1. #include <iostream>
  2. #include <cmath>
  3. #include <set>
  4.  
  5. using namespace std;
  6.  
  7. int p = 0, prime[100001];
  8.  
  9. void build_seive(){
  10.     int n = sqrt(100001), a[100001] = {0};
  11.     for(int j = 3; j <= n; j+=2)
  12.         if(a[j] == 0)
  13.             for(int k = j*j; j < 100001; j += 2*j)
  14.                 a[k] = 1;
  15.  
  16.     prime[p++] = 2;
  17.     for(int j = 3; j < 100001; j += 2)
  18.         if(a[j] == 0) prime[p++] = j;
  19.     return;
  20. }
  21.  
  22. int find_ans(int mask){
  23.     int counts = 0, maxi = 0;
  24.     for(int j = 1; j <= 30; j++)
  25.         if((1 << j) & mask){
  26.             counts ++;
  27.             maxi = j;
  28.         }
  29.     //cout << maxi << " " << counts << endl;
  30.     if(counts == 1 || counts == 0){
  31.         if(mask % 2 != 0) return (mask - 1);
  32.         return mask;
  33.     }
  34.     set<int> s;
  35.     for(int j = 1; j <= maxi; j++)
  36.         s.insert(find_ans((mask >> j) | (mask & ((1 << j) - 1))));
  37.     int mex = 0;
  38.     while(s.find(mex) != s.end())
  39.         mex++;
  40.     return mex;
  41. }
  42.  
  43. int n, a[101];
  44.  
  45. void solve(){
  46.     int ans = 0;
  47.     for(int j = 0; j < p; j++){
  48.         int mask = 0;
  49.         for(int k = 0; k < n; k++){
  50.             int counts = 0;
  51.             while(a[k] % prime[j] == 0){
  52.                 counts++;
  53.                 a[k] /= prime[j];
  54.             }
  55.             mask = mask | (1 << counts);
  56.         }
  57.         if(mask > 1) ans ^= find_ans(mask);
  58.         // if(mask > 1) cout << mask << endl;
  59.     }
  60.  
  61.     for(int j = 0; j < n; j++)
  62.         if(a[j] != 1){
  63.             int mask = 0, curr = a[j];
  64.             for(int k = 0; k < n; k++){
  65.                 int counts = 0;
  66.                 while(a[k] % curr == 0){
  67.                     counts++;
  68.                     a[k] /= curr;
  69.                 }
  70.                 mask = mask | (1 << counts);
  71.             }
  72.             if(mask > 1) ans ^= find_ans(mask);
  73.         }
  74.  
  75.     if(!ans) cout << "Arpa\n";
  76.     else cout << "Mojtaba\n";
  77.     return;
  78. }
  79.  
  80. int main(){
  81.     build_seive();
  82.     cout << find_ans((1 << 30) - 1);
  83.     /*ios_base :: sync_with_stdio(false);
  84.     cin >> n;
  85.     for(int j = 0; j < n; j++)
  86.         cin >> a[j];
  87.     solve();
  88.     return 0;*/
  89. }
  90.  
Time limit exceeded #stdin #stdout 5s 16720KB
comments (?)
stdin
copy 
19
1 2048 1048576 524288 16 128 32 2 16384 131072 32768 4 33554432 134217728 268435456 8 8388608 536870912 16777216
stdout
copy 
Standard output is empty
https://ideone.com/Sggig7
language:
C++14 (gcc 8.3)
created:
6 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!