题目

定义\(f(i)\)为\(i\)的所有约数的异或和，给定 \(n(1\le 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;

}