牛客Wannafly挑战赛23 B.游戏
游戏
题目描述
小N和小O在玩游戏。他们面前放了n堆石子，第i堆石子一开始有c i颗石头。他们轮流从某堆石子中取石子，不能不取。最后无法操作的人就输了这个游戏。但他们觉得这样玩太无聊了，更新了一下规则。具体是这样的：对于一堆有恰好m颗石子的石头堆，假如一个人要从这堆石子中取石子，设他要取石子数为d，那么d必须是m的约数。最后还是无法操作者输。
现在小N先手。他想知道他第一步有多少种不同的必胜策略。一个策略指的是，从哪堆石子中，取走多少颗石子。只要取的那一堆不同，或取的数目不同，都算不同的策略。
现在小N先手。他想知道他第一步有多少种不同的必胜策略。一个策略指的是，从哪堆石子中，取走多少颗石子。只要取的那一堆不同，或取的数目不同，都算不同的策略。
输入描述:
第一行一个整数n。
接下来一行n个整数，分别代表每堆石子的石子数目。
数据保证输入的所有数字都不超过10^5，均大于等于1，且为整数。
输出描述:
一行一个整数代表小N第一步必胜策略的数量。
输入
10 47 18 9 36 10 1 13 19 29 1
输出
7
链接：https://www.nowcoder.com/acm/contest/161/B
来源：牛客网
预处理下SG值，然后枚举下每堆拿走约数。
1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 const int maxn = 100005; 5 int sg[maxn]; 6 int a[maxn]; 7 bool vis[maxn]; 8 9 void getSg() 10 { 11 12 sg[0]=0; 13 for(int i=1;i<maxn;i++) 14 { 15 memset(vis,0,sizeof(vis)); 16 17 for(int j=1;j*j<=i;j++) 18 { 19 if(i%j==0) 20 { 21 vis[sg[i-j]]=1; 22 vis[sg[i-i/j]]=1; 23 } 24 } 25 26 for(int j=0;j<maxn;j++) 27 { 28 if(vis[j]==0) 29 { 30 sg[i]=j; 31 break; 32 } 33 } 34 } 35 } 36 37 int main() 38 { 39 getSg(); 40 int n; 41 scanf("%d",&n); 42 int sum = 0; 43 for(int i=1;i<=n;i++) 44 { 45 scanf("%d",&a[i]); 46 sum ^= sg[a[i]]; 47 } 48 int ans = 0; 49 for (int i = 1; i <= n; ++i) 50 { 51 sum ^= sg[a[i]]; 52 for (int j = 1; j * j <= a[i]; ++j) 53 { 54 if (a[i] % j == 0) 55 { 56 if (!(sg[a[i] - j] ^ sum)) 57 ans++; 58 if (j * j != a[i] && !(sg[a[i] - a[i] / j] ^ sum)) 59 ans++; 60 } 61 } 62 sum ^= sg[a[i]]; 63 } 64 printf("%d\n",ans); 65 return 0; 66 }
