自动搬运

查看原文

来自洛谷，原作者为

	Zzzcr **

搬运于2025-08-24 23:01:54，当前版本为作者最后更新于2024-08-10 19:24:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

upd：为防止歧义换了个变量名。

提供一个唐氏做法，不需要莫比乌斯反演。

首先把原式放到一起：

这个 $\gcd^k$ 和 $\oplus$ 看着都比较丑，考虑先枚举 $\gcd$，记作 $d$，只需要对于每个 $d$，求得 $i\oplus j$ 和 $j$ 都是 $d$ 的倍数的合法 $(i, j)$ 个数，记作 $r_d$，并做简单容斥就能求出答案，于是只需要考虑如何快速求出每个 $r_d$。

令 $x=i\oplus j$，我们可以容易的找到一种表述 $r_d$ 的方式，即：

考虑优化这个计算过程。

考虑维护一个序列 $a$，枚举 $d$，再在每个 $x$ 处做单点 $+1$。发现对于每对 $(x,i)$，$a_{x\oplus i}$ 会对 $r_d$ 造成贡献，当且仅当 $x\oplus i \le n$。我们当然可以通过枚举 $i$ 来做到 $O(n^2 \log{n})$，但这并不够优秀，回顾一下刚才对 $a$ 进行的操作，只有单点 $\pm1$，全局下标 $\operatorname{xor}$ 和区间求和，这显然可以使用线段树优化，于是我们便用 $O(n\log^2{n})$ 的复杂度解决了此题。