【牛客7872 D】尼姆博弈
题意
A和B玩游戏,给n个数,每次能对一个数进行操作,如果一个数是1那么不能对它进行操作。每次操作可以选择这个数x大于1的因子a,把这个数变成x/a。最后无法操作的人输。
问谁能赢?
题解
这是一道比较裸的尼姆博弈题,尼姆博弈是n堆石子,每堆石子有一定数量的石子,每次可以取一堆中一部分石子或者整堆取走,但是不能不取。对应到这道题目里,选择一个>1&&<自身的因此就相当于取走了一部分石子,选择自身这个因子就相当于直接整堆取走。那么每堆石子有多少个呢,答案就是这个数的质因子个数。然后根据尼姆博弈的结论,判断异或和是否为0,若为0则先手必败,反之则先手必胜。
Code
/**************************** * Author : W.A.R * * Date : 2020-10-31-20:53 * ****************************/ /* */ #include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> #include<queue> #include<map> #include<unordered_map> #include<stack> #include<string> #include<set> #define mem(a,x) memset(a,x,sizeof(a)) using namespace std; typedef long long ll; const int maxn=1e6+10; const ll mod=1e9+7; int main(){ ll n,ans=0,x;scanf("%lld",&n); for(ll i=1;i<=n;i++){ scanf("%lld",&x); ll sum=0; for(ll j=2;j*j<=x;j++)while(x%j==0)x/=j,sum++; if(x>1)sum++; ans^=sum; } if(ans)printf("CC yyds!\n"); else printf("TT txdy!\n"); return 0; }