题解：P3791 普通数学题

· · 题解

前言

在课上 @grass8cow 老师表演了 5min 切黑，可惜失败，被卡常了，好在卡了15min 后过去了 %%%

正文

简要题意

给定 n,m,x 求 \sum\limits_{i=0}^{n}\sum\limits_{j=0}^{m} d(i \oplus j \oplus x)

$1 \le n,m,x \le 10^{10}

解法

首先你会发现异或这个运算非常恶心，对于直接求约数十分困难。

不如考虑拆贡献！

对于每一个可能是出现的 i \oplus j \oplus x，我们将它设为 p，设它的出现次数为 K_p 设所有可能出现的 p 的集合为 P。

那么问题的答案就变为 \sum _{p\in P} d(p) \times K_p。

对于枚举异或运算可能会出现的数，我们很容易想到数位dp

我们因为 x 是固定的，我们先不考虑它，然后将 i \oplus j 拆成 i 和 j，再考虑朴素的从上往下 dp。

分别设后面 i 和 j 的后 x-1 与 y-1 位顶着上限，而第 x 与 y 位小于上限，则剩下的位置都可以随便填！

为了讨论方便，我们不妨定义一下 x 和 y 的位置关系，x \le y。

对于前 x-1 时，后面的部分，两个数都能随便取，有 2^{x-1} \times 2^{x-1} = 4^{x-1} 种情况，对于异或完之后这部分所有的 2^{x-1} 情况都能取到，所以每种数出现过 \frac{4^{x-1}}{2^{x-1}}=2^{x-1} 次。

当在 x \sim y-1 时 i 是固定的，而 j 随便取，有 1^{x-1} \times 2^{x-1} = 2^{x-1} 种情况，显然对于异或完还是能取到所有的 2^{x-1} 情况，所以每种数出现过 \frac{2^{x-1}}{2^{x-1}}=1 次。

对于后面的只有一种情况，且仅出现 1 次。

最后还有个小尾巴，求 d！

求 d 其实是幼儿园数学题，非常好求。

\sum\limits_{i=1}^n d(i)=\sum\limits_{i=1}^n \sum\limits_{j=1}^n (j\mid i)=\sum\limits_{i=1}^n \lfloor\frac{n}{i}\rfloor

这个显然可以数论分块！

总复杂度 O(\sqrt{n} \log^2 n)

注意常数！小心不要像牛吃草老师被卡常！