#651(Div.2)C.NumberGame(博弈论,思维)


题目描述

Ashishgup and FastestFinger play a game.
They start with a number n and play in turns. In each turn, a player can make any one of the following moves:
Divide n by any of its odd divisors greater than 1.
Subtract 1 from n if n is greater than 1.
Divisors of a number include the number itself.
The player who is unable to make a move loses the game.
Ashishgup moves first. Determine the winner of the game if both of them play optimally.

Input

The first line contains a single integer t (1≤t≤100) — the number of test cases. The description of the test cases follows.
The only line of each test case contains a single integer — n (1≤n≤109).

Output

For each test case, print “Ashishgup” if he wins, and “FastestFinger” otherwise (without quotes).

Example

input
7
1
2
3
4
5
6
12
output
FastestFinger
Ashishgup
Ashishgup
FastestFinger
Ashishgup
FastestFinger
Ashishgup

Note

In the first test case, n=1, Ashishgup cannot make a move. He loses.
In the second test case, n=2, Ashishgup subtracts 1 on the first move. Now n=1, FastestFinger cannot make a move, so he loses.
In the third test case, n=3, Ashishgup divides by 3 on the first move. Now n=1, FastestFinger cannot make a move, so he loses.
In the last test case, n=12, Ashishgup divides it by 3. Now n=4, FastestFinger is forced to subtract 1, and Ashishgup gets 3, so he wins by dividing it by 3.

题目大意

给定一个正整数 n,有两种操作:
(1)用 n 的一个大于 1 的奇因子除 n;(2)如果 n>1 将 n 减 1。
两个人玩游戏,每次每个人可以选择一个操作,最后谁不能操作谁就输。问谁会赢。

题目分析

这是一个博弈论的题目,有两条分支。
1是一个必败态,由1可以推出两个必胜态:2和奇数(这就是两条分支)。

  1. 2这条分支:
    由2这条分支可以推出,2*一个素数 (素数>2)是一个必败态。(先手除以该素数,会给对手留下2这个必胜态;而-1操作则会给对手留下奇数这个必胜态)
    进而可以推出,2 * 一个素数^n (素数>2)是一个必败态。(先手可以直接除以这个素数的n-1次方,留给对手2*一个素数的必败态)
    分支1:1(0) -> 2(1) -> 2*素数(0) -> 2*素数^n(1)
  2. 奇数这条分支:
    由奇数这条分支可以推出,2^n(n>1)是必败态。(因为2n没法除以奇数了,只能选择-1操作,然后就变成了奇数)
    进而可以推出,2^n * 某个奇数是必胜态。(先手可以直接除以这个奇数,然后就给对方留下了2n的必败态)
    分支2:1(0)-> 奇数(1) -> 2^n(0) -> 2^n*奇数(1)
代码如下
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include  
#include 
#include 
#define LL long long
using namespace std;
const int N=2e3+5;
bool is_prime(int x)
{
	for(int i=2;i<=x/i;i++)
		if(x%i==0) return false;
	return true;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		if(n==1) {puts("FastestFinger"); continue;}
		if(n&1||n==2) {puts("Ashishgup"); continue;}
		bool flag;
		if(n%4==0)	//分支2
		{
			while((n&1)==0) n>>=1;
			if(n==1) flag=false;
			else flag=true;
		}
		else	//分支1
		{
			n>>=1;
			if(is_prime(n)) flag=false;
			else flag=true;
		}
		if(flag) puts("Ashishgup");
		else puts("FastestFinger");
	}
	return 0;
}