D. Deleting Divisors Codeforces Round #726 (Div. 2)

题意:博弈论.给你一个数字n,每个回合,每名玩家可以挑选一个n的因子d,然后让 n = n − d n = n-d n=n−d.要求 d ! = 1 , d ! = n d!=1,d!=n d!=1,d!=n.求给定的n,谁必胜. 思路:很容易观察到,只要一个玩家拿到一个素数,那么它就输了,因为没有除了1和n的因子了.所以在n是素数情况下,2*n一定是一个必胜态. 接下来需要一点思维的转换了,思考减去d带来的影响.我们知道,所有的素数除了2以外一定是一个奇数.每次减法带来的影响就是把一个d减去. 如果n是一个偶数,那么d可以是一个偶数,可以是一个奇数,可以让对手持有奇数,有偶数的状态. 若n是一个奇数,那么d一定是一个奇数.对手只能得到一个偶数. 不考虑是2的状态,我们发现最后持有奇数的情况最后一定会变为一个素数的状态.所以持有奇数的情况一定是先手必输的. 那么考虑n是偶数的状态,先手一定可以使得对手持有奇数.除非你没有奇数的因子,也就是全部是2的指数的形式.否则你总是可以去掉一个奇数的 所以,偶数情况又分为:1.不是2的指数形式,先手必胜.

/*
 Alcie先手
 初始数字为n,每个回合挑选n的一个因子d. d!=1,d!=n
 然后 n-=d.
 不能行动的人判负. 
*/
#include
using namespace std;
const int maxn = 3e5+5;
const int INF = 1e9+7;
typedef long long ll;
double eps = 1e-6;
typedef pair pii;
bool equal(double a,double b){
	return fabs(a-b)>T;
	while(T--){
		ll n;cin>>n;
		if(n&1||n==2){
			cout