Advertisement
ismaeil

C. Number Game

Jun 21st, 2020
143
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.31 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef pair<int,int> ii;
  4.  
  5. const int MaxN = 1e9 + 2e2;
  6. const int N = (int)sqrt(MaxN) + 1;
  7. map<ii ,int> Memo;
  8. vector<int> Div;
  9. int n;
  10.  
  11. int calc(int n ,bool T) {
  12.     //  T = Ashishgup
  13.     // !T = FastestFinger
  14.  
  15.     int &Re = Memo[ {n,T} ];
  16.  
  17.     if(Re != 0) return Re;
  18.     if( n % 2 &&  T ) return Re = +1;
  19.     if( n % 2 && !T ) return Re = -1;
  20.  
  21.     int Res = -1;
  22.     for(auto i : Div){
  23.         if( i <= n && n % i == 0) {
  24.             if( (n / i) % 2 == 0 ){
  25.                 Res = calc(n / i ,!T);
  26.                 if( Res == 1 )
  27.                     break;
  28.             }
  29.         }
  30.     }
  31.     if( Res == -1 ) Res = calc(n-1 ,!T);
  32.     return Re = Res;
  33. }
  34.  
  35. void Solve(){
  36.     scanf("%d" ,&n);
  37.  
  38.     for(int i=2 ; i <= (int)sqrt(n) + 1 ; i ++){
  39.         if(n % i == 0) {
  40.             if( i & 1 )
  41.                 Div.push_back(i);
  42.             if( (n / i) & 1 && (n / i) > 1 )
  43.                 Div.push_back(n/i);
  44.         }
  45.     }
  46.  
  47.     bool Ashishgup     = true;
  48.     bool FastestFinger = false;
  49.  
  50.     Memo[ {1 ,Ashishgup} ]     = -1;
  51.     Memo[ {1 ,FastestFinger} ] = +1;
  52.     int Ans = calc(n ,1);
  53.  
  54.     puts( (Ans > 0) ? "Ashishgup" : "FastestFinger" );
  55.     Div.clear();
  56. }
  57.  
  58. int main() {
  59.     int Tc; scanf("%d" ,&Tc);
  60.     while( Tc-- ) Solve();
  61.     return 0;
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement