题目

定义(f(i))为(i)的所有约数的异或和，给定 (n(1le n le 10^{14})) ，求(f(1) xor f(2) xor f(3) xor…xor f(n)) （其中(xor)表示按位异或）

思路

首先考虑到枚举因数(x)，然后算出他是小于等于(n)的数字中(x)的倍数的个数,即(lfloor frac{n}{x} rfloor),然后根据奇偶性判断是否要异或(x)

这样复杂度是(o(n))的，看到(frac{n}{x})很容易想到数论分块。

然后问题就是如何快速查询连续区间的异或和。

设(s[x]=1^wedge2^wedge3…^wedge x)
那么区间([l,r])的异或和就是(s[r]^wedge s[l – 1])

然后对于(s)数组打个表如下

可以发现在模(4)意义下是有规律的。然后就可以(o(1))计算连续区间异或和了。

代码

/* * @author: wxyww * @date:   2019-03-24 14:06:25 * @last modified time: 2019-03-24 14:23:58 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> using namespace std; typedef long long ll;  ll read() {     ll x=0,f=1;char c=getchar();     while(c<'0'||c>'9') {         if(c=='-') f=-1;         c=getchar();     }     while(c>='0'&&c<='9') {         x=x*10+c-'0';         c=getchar();     }     return x*f; } ll n; ll query(ll l) {     if(l % 4 == 1) l = 1;     else if(l % 4 == 2) ++l;     else if(l % 4 == 3) l = 0;     return l; } int main() {     n = read();     ll ans = 0;     for(ll l = 1,r;l <= n;l = r + 1) {         r = n / (n / l);         if((n / l) & 1)         ans ^= query(l - 1) ^ query(r);     }     cout<<ans;     return 0; }