C. Number Game(博弈)

Problem - 1370C - Codeforces

Ashishgup和FastestFinger玩一个游戏。

他们从一个数字n开始，轮流玩。在每个回合中，玩家可以做以下任何一个动作。

用n除以任何大于1的奇数除数。
如果n大于1，则从n中减去1。
一个数字的除数包括该数字本身。

无法走棋的玩家就输掉了比赛。

Ashishgup先走。如果两人都以最佳状态下棋，则确定游戏的赢家。

输入
第一行包含一个整数t（1≤t≤100）--测试案例的数量。接下来是测试用例的描述。

每个测试用例的唯一一行包含一个整数--n（1≤n≤109）。

输出
对于每个测试案例，如果他赢了，就打印 "Ashishgup"，否则就打印 "FastestFinger"（不带引号）。

题解:
首先

1F赢

2A赢

如果n > 2 并且n%2==1 A赢

剩下就只有n > 2并且n%2 == 0的情况了

一个整数可以分解为一些奇数与一些偶数相乘

当然奇数*奇数仍为奇数,偶数*偶数仍为偶数

我们可以理解为这样

j为奇数 o为偶数

(一).

j * j *..*j * 2 ==n

这种情况我们要看前面有几个奇数

如果只有1个,那么F是必赢的,(只有6)无论怎么操作F是必赢的

如果有两个以上,我们可以让其变成6的情况,这样A必赢

(二).

j *j * .... * o(!=2类似(4,8,16)) == n

如果我们直接可以除完所有j数,一定是A赢

总结下来就是

	for(int i = 2;i <= k;i++)
	{
		if(n%i)
		{
			continue;
		}
		if(i%2&&(n/i)!=2)
		{
			f = 1;
		}
		if((n/i)%2&&(i!=2))
		f =1;
	}

换句话讲,只要n中有一个奇因数,并且n/这个奇因数不为2,就是A赢

完整代码(所有情况)

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
int a[200050];
int b[200050];
void solve()
{
	int n;
	cin >> n;
	if(n == 1)
	{
		cout<<"FastestFinger\n";
		return ;
	}
	if(n == 2)
	{
		cout<<"Ashishgup\n";
		return ;
	}
	if(n%2)
	{
		cout<<"Ashishgup\n";
		return ;
	}
	int k = sqrt(n);
	int f = 0;
	for(int i = 2;i <= k;i++)
	{
		if(n%i)
		{
			continue;
		}
		if(i%2&&(n/i)!=2)
		{
			f = 1;
		}
		if((n/i)%2&&(i!=2))
		f =1;
	}
	if(f)
	{
		cout<<"Ashishgup\n";;
	}
	else
	{
		cout<<"FastestFinger\n";		
	}
}
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		solve();
	}
}