问题描述
定义 f(i) 为 i 的所有约数的异或和，给定 n(1≤n≤10^14) ，求 f(1) xor f(2) xor f(3) xor...xor f(n)（其中xor表示按位异或）
输入格式
一行，一个整数n。
输出格式
一行，一个整数为答案。
样例输入
4
样例输出
7
解析
一眼数论分块，然后……然后呢？
问题在于我们如何在O(1)的时间内求出区间异或和。设(sum[i])表示从(1)到(i)的异或和的值。那么，由异或的性质，我们有：
[l xor l+1 xor ...... xor r=sum[r] xor sum[l-1]
]
所以，我们需要在O(1)的时间内求出(sum[i])。接下来是思维过程：
首先，完全不知所措。（什么玩意）
然后，陷入迷茫。
突然，想到自己最近的周总结里写了这么一句话
虽然51nod上有很多怪题（比如打表是正解之类的）
然后……就没了。
打表(sum[i])之后，可以发现有一个在4的剩余系中的规律。
代码
#include <iostream>
#include <cstdio>
using namespace std;
long long n,ans;
long long l,r;
long long get(long long x)
{
if(x%4==1) return 1;
else if(x%4==2) return x+1;
else if(x%4==3) return 0;
else return x;
}
int main()
{
cin>>n;
for(l=1;l<=n;l=r+1){
r=n/(n/l);
if((n/l)%2) ans=ans^get(l-1)^get(r);
}
cout<<ans<<endl;
return 0;
}