题目
定义(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; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/604629.html