fork download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int states[22], prime[1000001] = {0};
  6.  
  7. void build_states(){
  8.     states[1] = 0;
  9.     states[2] = 1;
  10.     for(int j = 3; j < 22; j++){
  11.         int ans = 0;
  12.         for(int i = 1; i <= (j/2); i++){
  13.             int curr = states[i] ^ states[j - i];
  14.             curr = 1 - curr;
  15.             ans = max(ans, curr);
  16.         }
  17.         states[j] = ans;
  18.     }
  19.     return;
  20. }
  21.  
  22. void build_seive(){
  23.     prime[2] = 2;
  24.     prime[1] = 1;
  25.     for(int j = 4; j < 1000001; j += 2)
  26.         prime[j] = 2;
  27.  
  28.     for(int i = 3; i < 1001; i += 2)
  29.         if(prime[i] == 0){
  30.             prime[i] = i;
  31.             for(int j = i*i; j < 1000001; j += i*2)
  32.                 prime[j] = i;
  33.         }
  34.     return;
  35. }
  36.  
  37. int num_of_fact(int x){
  38.     int ans = 0;
  39.     while(x != 1){
  40.         int curr = prime[x];
  41.         while(x % curr == 0){
  42.             ans ++;
  43.             x /= curr;
  44.         }
  45.     }
  46.     return ans;
  47. }
  48.  
  49. int main(){
  50.     build_states();
  51.     build_seive();
  52.  
  53.     int t;
  54.     cin >> t;
  55.     while(t--){
  56.         int n, ans = 0;
  57.         cin >> n;
  58.         while(n--){
  59.             int x;
  60.             cin >> x;
  61.             x = num_of_fact(x);
  62.             //cout << x << " ";
  63.             ans ^= states[x];
  64.         }
  65.         if(ans == 1) cout << "Appu\n";
  66.         else cout << "Friend\n";
  67.     }
  68.     return 0;
  69. }
  70.  
Success #stdin #stdout 0s 19144KB
comments (?)
stdin
copy 
1
2
2 4
stdout
copy 
Appu
https://ideone.com/LFGknR
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!