CodeForces-1537D Deleting Divisors 博弈

CodeForces-1537D Deleting Divisors 博弈

题意

给定数(n),每次可以删除(n)的除了1和本身以外的因子，如果不能操作就算输

分析

这题从删去的因子的奇偶性来讨论比较方便

将数分为三类：
1.奇数

2.偶数且(n = 2^k)

3.偶数且(n eq 2^k)

若是奇数，那么它的因子都是奇数，且减去一个奇数因子后就会变为偶数且( eq 2^k) ，而我们总是希望给出的数是奇数，因为无法移动的局面一定是1或者质数的局面，而除2以外所有质数都是奇数

若是偶数且(n eq 2^k) 我们一定会减去奇因子让它变成局面1

因此如果是局面1 必败，如果是局面3 必胜

如果是局面2，显然每次只能减去(2^{k_1}) ，(2^k- 2^{k_1} = 2^{k_1}(2^{k-k_1}))是偶数，一定不希望转移到局面3，因此只能令(k - k_1 = 1) ，因此这种情况只要讨论(k)的奇偶性

代码

#include<bits/stdc++.h>
#define pii pair<ll,ll>
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef vector<int> VI;

inline ll rd(){
    ll x;
    scanf("%lld",&x);
    return x;
}

const int MOD = (int)1e9 + 7;

inline int mul(int a,int b){
    int res = (ll)a * b % MOD;
    if(res < 0) res += MOD;
    return res;
}


inline void sub(int &a,int b){
    a -= b;
    if(a < 0) a += MOD;
}


inline int ksm(int a,int b = MOD - 2,int m = MOD){
	int ans = 1;
	int base = a;
	while(b){
		if(b & 1) ans = mul(ans,base);
		base = mul(base,base);
		b >>= 1;
	}
	return ans;
}

int main(){
	int T = rd();
	while(T--){
		int n = rd();
		if(n & 1) {
			puts("Bob");
		}
		else if(((n - 1) & n) == 0){
			int cnt = __builtin_popcount(n - 1);
			if(cnt & 1) puts("Bob");
			else puts("Alice");
		}	
		else puts("Alice");
	}
}