题面

对于给定的 nn ，计算：

(n mod 1)⊕(n mod 2)⊕⋯⊕[n mod (n−1)] (n \bmod 1) \oplus (n \bmod 2) \oplus \dots \oplus [n \bmod (n - 1)]

其中 ⊕\oplus 表示按位异或。

数据范围： n≤1012n \le 10^{12}

题面链接：CCPC2018 Hangzhou Problemset（L 题）

提交链接：HDUOJ 6275: Mod, Xor and Everything

由于 HDUOJ 卡常丧心病狂，建议读者前往 LibreOJ 6344: 异或和 提交（注意输入格式略微存在出入）。

分析

对于异或运算，我们不妨依据位运算的位独立性对于其二进制下的每一位逐位考虑。

对于数 nn ，其二进制第 kk 位上的值为：

⌊n2k⌋(mod2) \left\lfloor \frac{n}{2^k} \right\rfloor \pmod 2

那么，对于第 kk 位，经过题目中异或运算后这一位上的答案为：

∑i=1n⌊n mod i2k⌋(mod2) \sum\limits_{i = 1}^{n} \left\lfloor \frac{n \bmod i}{2^k} \right\rfloor \pmod 2

我们对其做一点小小的变换：

∑i=1n⌊n mod i2k⌋(mod2)=∑i=1n⌊n−⌊ni⌋i2k⌋(mod2) \begin{aligned} & \sum\limits_{i = 1}^{n} \left\lfloor \frac{n \bmod i}{2^k} \right\rfloor \pmod 2 \\ = & \sum\limits_{i = 1}^{n} \left\lfloor \frac{n - \left\lfloor \frac{n}{i} \right\rfloor i}{2^k} \right\rfloor \pmod 2 \end{aligned}

我们发现这个式子非常类似于类欧几里德可解决的 ff 式子（有一点不一样，但是后文会通过一些变换使其一样）。有关类欧几里德算法的相关内容可参考我的另一篇博客：浅谈类欧几里德算法。

至于 ⌊ni⌋\left\lfloor \frac{n}{i} \right\rfloor ，我们可以对其进行整除分块。

对于满足 ⌊ni⌋=t\left\lfloor \frac{n}{i} \right\rfloor = t 的某一块，我们记块的最左端为 ll ，最右端为 rr ，显然有：

⌊nl⌋=⌊nr⌋=t \left\lfloor \frac{n}{l} \right\rfloor = \left\lfloor \frac{n}{r} \right\rfloor = t

以及：

n mod r=n−⌊nr⌋r=n−tr \begin{aligned} n \bmod r & = n - \left\lfloor \frac{n}{r} \right\rfloor r \\ & = n - tr \\ \end{aligned}

那么对于这一块内求和：

∑i=lr⌊−ti+n2k⌋=∑i=−r−l⌊ti+n2k⌋=∑i=0r−l⌊t(i−r)+n2k⌋=∑i=0r−l⌊ti+(n−tr)2k⌋=∑i=0r−l⌊ti+(n mod r)2k⌋=f(t,n mod r,2k,r−l) \begin{aligned} \sum\limits_{i = l}^{r} \left\lfloor \frac{-ti + n}{2^k} \right\rfloor = & \sum\limits_{i = -r}^{-l} \left\lfloor \frac{ti + n}{2^k} \right\rfloor \\ = & \sum\limits_{i = 0}^{r - l} \left\lfloor \frac{t(i - r) + n}{2^k} \right\rfloor \\ = & \sum\limits_{i = 0}^{r - l} \left\lfloor \frac{ti + (n - tr)}{2^k} \right\rfloor \\ = & \sum\limits_{i = 0}^{r - l} \left\lfloor \frac{ti + (n \bmod r)}{2^k} \right\rfloor \\ = & f(t, n \bmod r, 2^k, r - l) \end{aligned}

简而言之，我们首先通过整除分块得到每一块的 ll 和 rr ，并求出这一段中每一位对应的结果，最后将所有段的结果求和并将不同位“组装”起来就是最终答案了。

复杂度：O(nlog⁡n)\mathcal{O}(\sqrt{n}\log{n}) 。

这道题卡常呜呜呜。

在 nn 比较小的时候，O(n)\mathcal{O}(n) 暴力是比类欧 O(nlog⁡n)\mathcal{O}(\sqrt{n}\log{n}) 跑得还要快的…… 故考虑设定一个阈值 limlim ，当 ii 不大于 limlim 的时候跑暴力，大于 limlim 的时候跑类欧。对于本弱写的代码，实测得到 limlim 大致取值在 2×107∼4×1072 \times 10^7 \sim 4 \times 10^7 范围内时可以在 HDUOJ 上卡进时限。而在 LibreOJ 上这个范围就要宽很多了。

最后附上 我的代码 以供参考。

%%%