数字游戏

题目链接：ybt高效进阶6-5-2

题目大意

给你一个数，两个人轮流对数进行操作，谁先不能操作，谁就输了。
操作是将它除以一个大于 1 的任意一个奇数因子，或者在它 >1 的时候，也可以选择把它减一。
问你是先手必胜还是先手必败。

思路

首先发现 $1$ 的话就是先手必败，$2$ 就是先手必胜。

接着发现如果是非 $1$ 奇数就直接先手必胜。（直接除这个数变成 $1$）
然后接着讨论偶数，发现是不能 $-1$ 的，因为减了就变成奇数，就败了。（$2$ 已经讨论过，所以不算在内）

那就只能除奇数因子，那就有如果是 $n=2^x$ 且 $x>1$ 的数，那就没得除，就先手必败。

那我们继续分析，由于 $2^1$ 是必胜而 $2^x(x>1)$ 必败，我们考虑分开来讨论。
如果只有一个 $2$，那就看奇数，如果奇数可以通过除一次让它变成质因子，那就是必胜，否则就是必败。（要满足这个其实就是让它原本不是质因子就可以了）
那如果有多个 $2$，那你只要把奇数因子全部除掉，那给对面的就是 $2^x(x>1)$，那就是后手必败，也就是先手必胜了。
那这里其实可以总结一下，其实就是当 $n=2\ast W$，如果 $W$ 是质因子就是先手必败，否则就是先手必胜。

然后就可以了。

代码

#include<cstdio>

using namespace std;

int T, n;

bool is_prime(int n) {
	for (int i = 2; 1ll * i * i <= n; i++)
		if (n % i == 0) return 0;
	return 1;
} 

bool fang2(int n) {
	if ((n & (-n)) == n) return 1;
	return 0;
}

bool ck(int n) {
	if (n == 1) return 0;
	if (n == 2) return 1;
	if (n & 1) return 1;
		else n >>= 1;
	if (fang2(n)) return 0;//2^n 的情况
	if (is_prime(n)) return 0;
		else return 1;
}

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		if (ck(n)) printf("Ashishgup\n");
			else printf("FastestFinger\n");
	}
	
	return 0;
}