Introduction

In this post, I will try to illustrate the approach to solve the problem (Number Game). Problem code on codeforces is 1370C. This tutorial will require a beginner level of c++.

Problem statement explanation

The problem is composed of a game played by 2 persons Ashishgup and FastestFinger. Each of them tries to win the game so they try to play optimally as possible to win. In the beginning, the two players will have a number n. Each player tries to be the last one to play so he could win.
The operations that each player could do to n are:

• subtract 1 from n.
• divide n by one of its odd divisors.

  For example

  we have n = 30, the player could divide n by 3, 5 or 15 as they are the odd divisors of n.

Note

Ashishgup is the one who starts the game.

Solution

In the beginning, we should look at the maximum value of n to determine our solution complexity. n here is 10^9 which will require a solution faster than o(n).

base cases

• We should by a simple observation see that whenever n is odd, Ashishgup can win. As, he could divide the numbers by itself leaving for FastestFinger only 1 so he loses, and Ashishgup wins.
• whenever n is equal 1 Ashishgup will lose, and FastestFinger will win. Ashishgup won't be able to make a move.

So now, we will be left with only even n's. The key here is that Ashishgup will start and also that all prime numbers are odd except 2. The two of them is trying to avoid leaving one move for the other player. So when we have n=30, let's see some scenarios for Ashishgup selection of operations:

• He could make n-1 operation but that will leave FastestFinger with an odd number. So he will divide the number by itself, leaving for Ashishgup only 1 so he loses. Apparently not a good choice.
• He could divide n by 3. This will leave FastestFinger with 10. then FastestFinger must choose to divide by 5 as if he chooses the other operation he loses. so now n=2, and it is Ashishgup turn so he will minus 1 from it and win the game. This is a good choice.
• If he chooses to divide n by 5. he will lead to the same result as to divide by 3.
• If he chooses to divide by 15. In this case, he will lose, as he will leave FastestFinger with 2, and this makes FastestFinger win.
  So the best choice here is to divide by 3 or 5. So the key is to first get the number of 2's in n. then get the number of prime divisors of n. If n has no prime divisors other than 2 so this will definitely make FastestFinger win. Ashishgup will have only to make the n-1 operation which will make him lose.
  In the other case when there are odd divisors to n, then it is obvious for Ashishgup to win, he will have to take all the divisors to leave for FastestFinger only even number with no prime divisors. But that will raise another case when the only even number left is 2. In this situation, he will lose so the best thing in this situation is to take all odd divisors except one for FastestFinger to force him to choose it and Ashishgup wins. But wait! what if there is only one 2 and one odd divisor. In this situation, Ashishgup will lose in all cases.

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define all(v)   (v.begin()),(v.end())
int primeFactors(ll n)
{

    while (n % 2 == 0)
    {
        n = n / 2;
    }
    int ans = 0;
    // n must be odd at this point.  So we can skip
    // one element (Note i = i +2)
    for (int i = 3; i <= sqrt(n); i = i + 2)
    {
        // While i divides n, print i and divide n
        while (n%i == 0)
        {
            ans++;
            n = n / i;
        }
    }

   // This condition is to handle the case when n
   // is a prime number greater than 2
   if (n > 2)
        ans++;
   return ans;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie();
    cout.tie();

    int t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        if(n==1){
            cout<<"FastestFinger\n";
            continue;
        }
        if(n%2==1){
            cout<<"Ashishgup\n";
            continue;
        }
        if(n==2){
            cout<<"Ashishgup\n";
            continue;
        }
        int twos = 0;
        int odds = primeFactors(n);

        int num = 0;
        while(n%2==0){
            n/=2;
            num++;
        }
        if(odds==0)cout<<"FastestFinger\n";
        else if(num>1)cout<<"Ashishgup\n";
        else if(odds==1) cout<<"FastestFinger\n";
        else cout<<"Ashishgup\n";

    }
}