[51nod1984] 异或约数和

问题描述

定义 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\)的异或和的值。那么，由异或的性质，我们有：

所以，我们需要在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;
}

[51nod1984] 异或约数和

原文：https://www.cnblogs.com/LSlzf/p/12616774.html