题目的意思是给你若干个数字，两个游戏者轮流操作，每次可以将该数变为一个小于当前的一个约数，无法操作的游戏者fail。
和其他的博弈题目大同小异吧。
不同点有两个，逐一分析吧。
一、每次改变一个数只能改变为小于当前数的约数，所以相对来说Sg函数值得求法有点不同哦。自己打个表就可以发现这个题目的Sg函数值是该数的除了1以为的约数的个数。这样我们可以用一点数论的知识把Sg函数值搞定了。
二、题目还要对于必胜态，输出改变的标号最小的数。就是对于每一个数，异或判断是否可行就可以了。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #define maxn 5000005 5 using namespace std; 6 7 int sg[maxn]; 8 int a[100100],n,m,ans; 9 10 void init_sg() 11 { 12 memset(sg,0,sizeof sg); 13 for (int i=2; i<maxn; i++) 14 { 15 if (sg[i]) continue; 16 for (int k=1,j; maxn/k>=i; ) 17 for (k*=i,j=k; j<maxn; j+=k) sg[j]++; 18 } 19 } 20 21 int main() 22 { 23 int cas=0; 24 init_sg(); 25 while (scanf("%d",&n)!=EOF) 26 { 27 ans=m=0; 28 for (int i=1; i<=n; i++) scanf("%d",&a[i]),m^=sg[a[i]]; 29 for (int i=1; i<=n; i++) 30 { 31 if ((m^sg[a[i]])<sg[a[i]]) 32 { 33 ans=i; 34 break; 35 } 36 } 37 if (m) printf("Test #%d: Alice %d ",++cas,ans); 38 else printf("Test #%d: Bob ",++cas); 39 } 40 return 0; 41 }