Codeforces Round #651 (Div. 2) C. Number Game

题目：A(Ashishgup)和B(FastestFinger)两人做数字游戏,A先开始，任给一数字n规则如下：

①将n除以>=3的奇数（n必须整除此奇数）

②将n-1

③n>0，两人必须选择①或②轮流操作，一方不能继续进行，另一方即获得胜利

关键思想：当n=1 ,  n=₂× (x>1) 或n=2 * P(P>=3),P为质数时。B赢，其他情况A赢

1. 当n为奇数（n>1）；

A可以用n/n,剩下1留给B,A就获胜了

2.当n为偶数，并且不含有大于1的奇因子时；（n>2）

A没有选择，只能-1，B得到大于1的奇数，B获胜

3.n是偶数，并且含有一个或多个奇因子

如果n能整除4，A可以除以n最大的奇数因子，剩下₂× (x>1)留给B,A获胜；即为（₂×  * p）p为奇数，x>1

或者n为2*p(p为奇数且大于1)此时p有两种情况 ⑴p为质数 ⑵p=p1*p2(p1为奇数，p2为质数)

对于⑴A输B胜，对于⑵A选择除以p2，A胜

 

#include< bits/stdc++.h >
using namespace std;

const int N = 50000;

void player_1(){
	cout << "Ashishgup" << endl;
}

void player_2(){
	cout << "FastestFinger" << endl;
}

bool check_prime(int n){
	for(int i = 2; i < min(N, n); i++)
		if(n % i == 0)
			return 0;
	return 1;
}

int main(){
	int tc;
	cin >> tc;
	while(tc--){
		int n;
		cin >> n;
		bool lose = (n == 1);
		if(n > 2 && n % 2 == 0){
			if((n & (n — 1)) == 0)            //位运算判断是否为2的x次方
				lose = 1;
			else if(n % 4 != 0 && check_prime(n / 2))    //包含3种A赢的情况，1种A输的情况
				lose = 1;
		}
		if(lose)
			player_2();
		else player_1();
	}
}