首页 > 代码库 > CF 317D Game with Powers
CF 317D Game with Powers
典型的博弈题目
题意：
两个人从1~n中轮流取数，每次取到x时，则x的任意整数幂均不能再被取，最后谁取不了就输。
题解：
可以发现，对于该博弈游戏的子游戏是x的1~k次幂，进行上述规则下的博弈。
而子游戏的SG值只与个数有关，与x的值无关。而k最大只有30，故可以打表。
而游戏最终结果即所有子游戏异或值。
代码：（附打表程序）
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cstdlib>#include <cmath>#include <utility>#include <vector>#include <queue>#include <map>#include <set>#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)>(y)?(y):(x))using namespace std;bool pd[100005];int n;/*打表char SG[1100000000];int getsg(int S){ if(SG[S]!=-1) return SG[S]; bool hash[32]={0}; for(int i=1; i<=30; i++) if(S&(1<<(i-1))) { int tmS=S; for(int j=i; j<=30; j+=i) if(tmS&(1<<(j-1))) tmS-=1<<(j-1); hash[getsg(tmS)]=1; } for(int i=0; i<=30; i++) if(!hash[i]) return SG[S]=i;}void init(){ memset(SG,-1,sizeof(SG)); SG[0]=0; getsg((1<<30)-1); for(int i=1; i<=30; i++) printf("%d,",SG[(1<<i)-1]);}*/int SG[]={0,1,2,1,4,3,2,1,5,6,2,1,8,7,5,9,8,7,3,4,7,4,2,1,10,9,3,6,11,12,14};int main(){ scanf("%d",&n); long long ans=1; memset(pd,0,sizeof(pd)); long long i,cut=0; for(i=2; i<=floor(sqrt(n)); i++) if(!pd[i]) { int num=0; for(long long j=i; j<=n; j*=i) { if(j<=floor(sqrt(n))) pd[j]=1; else cut++; ++num; } ans^=SG[num]; } ans^=(n-i+1-cut)&1; if(ans==0) printf("Petya\n"); else printf("Vasya\n"); return 0;}
CF 317D Game with Powers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。