为公式2.
因为异或运算满足交换律和结合律，
所以公式 = p1^p2^……^pn^(1%1)^(1%2)^……(1%n)^(2%1)%(2%2)^……^(2%n)^……^(n%1)^(n%2)^……^(n%n)
=p1^p2^……^pn^(1%1)^(2%1)^……(n%1)^(1%2)^(2%2)^……^(n%2)^……^(1%n)%(2%n)^……^(n%n).
公式2=(1%1)^(1%2)^……(1%n)^(2%1)%(2%2)^……^(2%n)^……^(n%1)^(n%2)^……^(n%n)
=p1^p2^……^pn^(1%1)^(2%1)^……(n%1)^(1%2)^(2%2)^……^(n%2)^……^(1%n)%(2%n)^……^(n%n).
那么公式2再以后面模数分类结合。
可以的到模数从1-n的通项为Sk=(1%k)^(2%k)^.....(n%k).
那么k是从1-n取不同的数，然后公式2就为S1^S2.....^Sn。
关键是Sk的求解，每一个k，Sk=(1%k)^(2%k)^.....(n%k)，其中（n%k）的值只能取（0-k）,那没 （1，n）是连续的所以必定有周期，
由于a^a=0,a^0=a;
举个例子；假如n=9,k=4;
| 1 | 2 | 3 | 0 |
| 1 | 2 | 3 | 0 |
| 1 | |||
结果就是1，上边的两行a^a=0，所以只剩下1；
又如当n=25，k=7时。（1%7)、(2%7)……(25%7)的结果如下表。
|
1 |
2 |
3 |
4 |
5 |
6 |
0 |
|
1 |
2 |
3 |
4 |
5 |
6 |
0 |
|
1 |
2 |
3 |
4 |
5 |
6 |
0 |
|
1 |
2 |
3 |
4 |
|
|
|
上边的整行就是n/k;
下面剩下的就是n%k;
那么如果上面为偶数行&&(n%k)>=1的话那么最后的sk=1^...(n%k);
如果上面为偶数行&&n%k==0,那么sk=0;
如果上面为奇数行&&(n%k)==0，sk=1^...k;
如果上面为奇数行&&（n%k)>=1,那么sk=(n%k+1)^....k;
这样的话每个sk就很容易计算了。
1 #include<stdio.h> 2 #include<algorithm> 3 #include<stdlib.h> 4 #include<string.h> 5 #include<iostream> 6 #include<queue> 7 #include<math.h> 8 typedef long long ll; 9 ll a[1000005]; 10 ll dd[1000005]; 11 ll cc[1000005]; 12 int main(void) 13 { 14 ll i,j,k,p,q; 15 ll pp=0; 16 dd[0]=0; 17 while(scanf("%I64d",&k)!=EOF) 18 { 19 cc[k+1]=0; 20 for(i=1; i<=k; i++) 21 { 22 scanf("%I64d",&a[i]); 23 pp^=a[i]; 24 dd[i]=(dd[i-1]^i); 25 } 26 for(i=k; i>=0; i--) 27 { 28 cc[i]=cc[i+1]^i; 29 } 30 /*那么如果上面为偶数行&&(n%k)>=1的话那么最后的sk=1^...(n%k); 31 32 如果上面为偶数行&&n%k==0,那么sk=0; 33 如果上面为奇数行&&(n%k)==0，sk=1^...k; 34 35 如果上面为奇数行&&（n%k)>=1,那么sk=(n%k+1)^....k;*/ 36 for(i=1; i<=k; i++) 37 { 38 p=k/i; 39 q=k%i; 40 if(p%2==1) 41 { 42 pp^=(cc[i]^cc[q+1]); 43 } 44 else if(p%2==0) 45 { 46 pp^=dd[q]; 47 } 48 } 49 printf("%I64d\n",pp); 50 } 51 return 0; 52 }
codeforce-424C. Magic Formulas(数学)
原文：http://www.cnblogs.com/zzuli2sjy/p/5016948.html