题目链接

题目大意

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

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

解题思路

1.若n为质数

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

2.若n为奇数(奇合数)

此时可以将其写成n=a\times{}b,其中ab都是奇数;

如果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-1b都是奇数,转化为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;
}
分类: 补题

0 条评论

发表评论

邮箱地址不会被公开。 必填项已用*标注