当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 51nod97B 异或约束和

51nod97B 异或约束和

2019年03月25日  | 移动技术网IT编程  | 我要评论

特级血色愤怒战盔,凤凰卫视锵锵三人行,形考答案

题目

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

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网