题意:爱丽丝和鲍勃正在玩游戏。 他们轮流操作。有n个数字,a1,a2,…,an。每次,玩家分3 步进行游戏。 1.任意选择一个数字ai。 2.任意选择另一个数x(1≤x<ai)。 3. 用 gcd(ai,x) 替换数字 ai。 这里,gcd(u,v) 指的是 u 和 v 的最大公约数。 当玩家不能移动时,他/她就输掉了游戏。爱丽丝先走,她让你告诉她,如果两个玩家都有最佳策略,谁将赢得比赛。
思路:每次的操作都分为三步,要将其转化为自己的一个因数,那么对于某一个数字而言,它最多可操作的次数就取决于自己有多少个质因数。(NIM博弈问题)
accode:
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <map>
using namespace std;
typedef long long ll;
const int maxn = 1e7+10;
int n, m, a, cnt;
int num[maxn];
int prime[maxn];
bool f[maxn];
void find_prime(int n)
{
for(int i = 2; i <= n; i++)
{
if(!f[i])
prime[+cnt] = i,num[i] = 1;
for(int j = 1; j <= cnt && i * prime[i] <= n; j++)
{
f[i * prime[j]] = true;
num[i * prime[j]] = num[i] + 1;
if(i % prime[i] == 0)
break;
}
}
}
int main()
{
find_prime(maxn);
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
scanf("%d", &a);
int ans = num[a];
for(int i = 2; i <= n; i++){
scanf("%d", &a);
ans ^= num[a];
}
if(ans) printf("Alice\n");
else printf("Bob\n");
}
return 0;
}
|