首页 > 代码库 > ZOJ 3529

ZOJ 3529

2024-08-01 05:22:33   220人阅读

博弈问题

这一题其实就是Nim游戏

因为每一个数都可以写成N=p1^a1*p2^a2*...*pn^an(pi为素数)的形式

每次变成一个因数，就相当于取走一个或者多个pi

所以每一个number就相当于Nim中的有(a1+a2+..an)个石头

这样就变成了裸了Nim游戏

直接套模板

 1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 #include <string.h> 5 using namespace std; 6 const int inf=5000001; 7 bool isprime[5000001]; 8 int a[100002],prime[2000],m,n,num[100002]; 9 void getp(){　　　　　　　　//素数打表10     memset(isprime,1,sizeof(isprime));11     isprime[1]=0;12     int k=0;13     int f=(int)sqrt((double)inf);14     for(int i=2;i<f;i++){15         if(isprime[i]){16             prime[k++]=i;17             for(int j=i*i;j<inf;j+=i){isprime[j]=0;}18         }19     }20 21 }22 void getnum(){　　　　　　求（a1+a2+..）23     memset(num,0,sizeof(num));24     for(int i=1;i<=n;i++){25         if(isprime[a[i]]){num[i]=1;continue;}26         for(int j=0;prime[j]<=a[i];j++){27             if(isprime[a[i]]){num[i]++;break;}28             if(a[i]%prime[j])continue;29             while(a[i]%prime[j]==0){30                 num[i]++;31                 a[i]/=prime[j];32             }33         }34     }35 }36 int main()37 {38     int ks=1;39     getp();40     while(scanf("%d",&n)!=EOF){41         m=0;42         for(int i=1;i<=n;i++){43             scanf("%d",a+i);44         }45         getnum();46         for(int i=1;i<=n;i++){47             m=m^num[i];48         }49         if(m==0){printf("Test #%d: Bob\n",ks++);continue;}50         int i;51         for(i=1;i<=n;i++){52             if((m^num[i])<num[i])break;53         }54         if(i!=n+1)printf("Test #%d: Alice %d\n",ks++,i);55         else printf("Test #%d: Bob\n",ks++);56     }57     return 0;58 }

 

ZOJ 3529


联系
我们