P10855 Gcd with Xor 题解

· · 题解

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

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

首先把原式放到一起：

\sum_{i=1}^n{\sum_{j=1}^{i}\gcd(j,i\oplus j)^k}

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

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

r_d=\sum_{d\mid x}\sum_{t=x}^{n}[d\mid t\oplus x]

考虑优化这个计算过程。

考虑维护一个序列 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}) 的复杂度解决了此题。