题解：P3791 普通数学题

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

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

$d(i)$ 表示为 $i$ 的约数个数。

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

不如考虑拆贡献！

对于每一个可能是出现的 $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$ 其实是幼儿园数学题，非常好求。

这个显然可以数论分块！

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

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