题目大意
给你一个数字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;
}
0 条评论