题目链接：http://codeforces.com/problemset/problem/424/C
题目意思：给出 n 个数：p1, p2, ..., pn，定义：
q1 = p1 ^ (1 mod 1) ^ (1 mod 2) ^ (1 mod 3) ...^(1 mod n)；
q2 = p2 ^ (2 mod 1) ^ (2 mod 2) ^ (2 mod 3) ...^(2 mod n)；
...
qn = p3 ^ (n mod 1) ^ (n mod 2) ^ (n mod 3) ...^(n mod n)
Q = q1 ^ q2 ...^ qn
要求算出 Q
很明显，如果直接做绝对是超时的。在这里，非常感谢 yk 师弟不厌其烦地为我解释思路，虽然最后我并没有按他的思路做......
那么，不能直接算就需要从公式中找规律。首先要清楚的是，异或 ^ 运算满足交换律；所以可以先求出 p1 ^ p2 ^ ...^ pn，并且可以先求出第一列异或的结果，再跟第二列求出的异或结果异或...直到跟最后一列的结果异或。其次，假设 n 代表一个非零整数，有3条公式需要知道：（1）0 ^ n = n；（2）n ^ n = 0（可以推广到异或偶数次自身），（3） n ^ n ^ n = n（可以推广到异或奇数次自身）。 这3个公式对后面的的计算进行简化。
假设n = 5。接着请读者打竖看，即 1 mod 1, 2 mod 1， ...， 7 mod 1 地看。很明显这一列 异或之后 是等于0的！那么从第二列开始看： 第三列 第四列 第五列
1 mod 2 = 1 1 mod 3 = 1 1 mod 4 = 1 1 mod 5 = 1
2 mod 2 = 0 2 mod 3 = 2 2 mod 4 = 2 2 mod 5 = 2
3 mod 2 = 1 3 mod 3 = 0 3 mod 4 = 3 3 mod 5 = 3
4 mod 2 = 0 4 mod 3 = 1 4 mod 4 = 0 4 mod 5 = 4
5 mod 2 = 1 5 mod 3 = 2 5 mod 4 = 1 5 mod 5 = 0
观察这些数，可以得出每一列 mod 出来的结果都是比被 mod 数小的：第二列 mod 出来的结果都比 2 小 ； 第三列 mod 出来的结果都比 3 小；...第五列比 5 小。再观察发现，每一列 mod 出来的数是有周期性的。这时需要用到上面所说的后两条公式了。需要知道这些周期究竟是计数还是偶数，如果是偶数，相当于根本没有做过异或操作；否则异或一次。周期数的计算可以用这个公式 (n-n%i)/i 求出 。最后要处理的是最后面的那些不成周期的数究竟是什么，可以用到 n % i 来得出。（i 表示 每列中被mod的数）
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 using namespace std; 5 6 const int maxn = 1e6; 7 int num[maxn]; 8 9 int main() 10 { 11 int i, p, n, ans; 12 num[0] = 0; 13 for (i = 1; i <= maxn; i++) 14 num[i] = num[i-1] ^ i; // num[1] = 0^1; num[2] = 0^1^2; num[n] = 0^1^2...^n 15 while (scanf("%d", &n) != EOF) 16 { 17 ans = 0; 18 for (i = 0; i < n; i++) 19 { 20 scanf("%d", &p); 21 ans ^= p; // 先求出p1^p2^...^pn 22 } 23 for (i = 2; i <= n; i++) 24 { 25 int tmp = n - n % i; 26 if ((tmp/i) & 1) // tmp/i 表示有多少个周期数 27 ans ^= num[i-1]; 28 ans ^= num[n%i]; // 不成周期数的独立处理 29 } 30 printf("%d ", ans); 31 } 32 return 0; 33 }