51nod97B 异或约束和

题目

定义\(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;
}