题目链接

题目大意

给你一个数字n，对于n若存在因数a(a不等于1或n)，则可以将n替换为n-a

现在alice和bob轮流对这个数进行操作，如果一方无法操作则另一方胜利。求在双方采取最优策略的情况下，最终获胜的一方是谁？

解题思路

1.若n为质数

Bob必胜，此时Alice先手无法更改这个数

2.若n为奇数（奇合数）

此时可以将其写成n=a\times{}b，其中a和b都是奇数；

如果Bob选择每一手都重复Alice的操作，那么两轮过后会变成n=(a-2)\times{}b或者n=a\times{}(b-2)，显然此时的n依然是奇数。

根据数学归纳法易知，若n为奇数（奇合数）则可以转化成1\times{}1。

此时Bob必胜

3.若n为偶数（非2的幂次）

此时一定可以将其写成n=a\times{}b，其中a是偶数b是奇数。

Alice先手减去一个b，使之成为n=(a-1)\times{}b，其中a-1和b都是奇数，转化为2中的情况（Alice后手，必胜）

此时Alice必胜

4.若n为2的幂次

在n为偶数时，有一种情况无法写成3中形式，即n为2的幂次。

此时n=2^i，经过简单推理可以得出：n=2/8/32时Bob胜；n=4/16/64时Alice胜；

因此，当i为偶数时，Alice胜；当i为奇数时，Bob胜。

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int eps = 1e-8;
int T;
int n;
bool check(int x){
    for(int i=2;i*i<=x;i++){
        if(x%i==0) return 0;
    }
    return 1;
}
signed main(){
    cin>>T;
    while(T--){
        cin>>n;
        if(check(n)){ //n为质数
            cout<<"Bob"<<"\n";
            continue;
        }
        if(n%2==1){ //n为奇数
            cout<<"Bob"<<"\n";
        }
        else{ //n为偶数
            bool is_output=0;
            for(int i=1;;i++){ //枚举2^i
                if(abs(pow(2,i)-n)<=eps){
                    if(i%2==0) cout<<"Alice"<<"\n";
                    else       cout<<"Bob"<<"\n";
                    is_output=1;
                    break;
                }
                if(pow(2,i)>n) break;
            }
            if(!is_output) cout<<"Alice"<<"\n"; //如果n为偶数且不是2^i
        }
    }
    return 0;
}