http://www.lydsy.com/JudgeOnline/problem.php?id=3576
思路:由于数字巨大，因此N^2异或做法是过不了的，我们考虑将n个石子分成i堆，那么会有n%i堆n/i+1的石子，i-n%i堆n/i的石子。如果两个堆的石子数相同，那么他们异或起来就为0，因此，这两种石子堆，我们可以看做:每种至多只有1堆。这样就可以枚举n/i，然后可以避免计算很多重复的部分，时间复杂度为N^1.5
1 #include<algorithm> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<iostream> 6 #define M 100100 7 int T,F,n,sg[2000005],v[2000005],ans; 8 int read(){ 9 int t=0,f=1; 10 char ch=getchar(); 11 while (ch<‘0‘||ch>‘9‘) {if (ch==‘-‘) ch=-1;ch=getchar();} 12 while (‘0‘<=ch&&ch<=‘9‘){t=t*10+ch-‘0‘;ch=getchar();} 13 return t*f; 14 } 15 void init(){ 16 for (int i=0;i<F;i++) sg[i]=0; 17 for (int i=F;i<=100000;i++){ 18 for (int j=2,pos=0;j<=i;j=pos+1){ 19 pos=i/(i/j);int k=i/j; 20 int nk1=i%j,nk=j-nk1; 21 v[sg[(nk&1)*(k)]^sg[(nk1&1)*(k+1)]]=i; 22 if (j+1<=std::min(pos,i)){ 23 nk1=i%(j+1),nk=j+1-nk1; 24 v[sg[(nk&1)*(k)]^sg[(nk1&1)*(k+1)]]=i; 25 } 26 } 27 for (int j=0;;j++) 28 if (v[j]!=i){ 29 sg[i]=j; 30 break; 31 } 32 } 33 } 34 int main(){ 35 T=read();F=read(); 36 init(); 37 while (T--){ 38 n=read(); 39 ans=0;int x; 40 for (int i=1;i<=n;i++) 41 x=read(),ans^=sg[x]; 42 if (!T) printf("%d\n",(!ans)?0:1); 43 else printf("%d ",(!ans)?0:1); 44 } 45 }
原文：http://www.cnblogs.com/qzqzgfy/p/5592057.html