整理一下，不然再过三天就又忘了。

莫比乌斯反演的套路

emmm，因为我做过的题太少了，所以可能非常不全。

以下的式子都是用$\sum_{d \ | n} \mu(d) = [n = 1]$推出来的，想看"正规"形式的可以参考这里

如果不做特殊说明的话，$\frac{n}{k}$默认为下取整，保证$n < m$

常用性质

• $$\left \lfloor \frac{\left \lfloor \frac{x}{a} \right \rfloor}{b} \right \rfloor = \left \lfloor \frac{x}{ab} \right \rfloor$$

证明：设$y = \frac{x}{a}, z = \frac{x}{ab}$

显然$x= z * ab + c$，且$c < ab$

把$a$除掉，得到$y = z * b + \frac{c}{a}$，因为$c < ab$，因此$\frac{c}{a} < b$

那么$\frac{y}{b} = z$

• $\frac{n}{i}$对于不同的$i$最多只有$2\sqrt{n}$种不同的取值

证明：

当$i < \sqrt{n}$时显然成立

当$i > \sqrt{n}$时，$\frac{n}{i} < \sqrt{n}$，也成立

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

这类应该是最基础的问题

$$\begin{aligned} &\sum_{i = 1}^n \sum_{j = 1}^m gcd(i, j) = k \\ &\sum_{i = 1}^{\frac{n}{k}} \sum_{j = 1}^{\frac{m}{k}} [gcd(i, j)]\\ &\sum_{i = 1}^{\frac{n}{k}} \sum_{j = 1}^{\frac{m}{k}} \sum_{d \ | gcd(i, j)} \mu(d)\\ &\sum_{i = 1}^{\frac{n}{k}} \sum_{j = 1}^{\frac{m}{k}} \sum_{d \ | i} \sum_{d \ | j}\mu(d)\\ &\sum_{d = 1}^n \mu(d) \sum_{i = 1}^{\frac{n}{k}} \sum_{d \ | i} \sum_{j = 1}^{\frac{m}{k}}\sum_{d \ | j} 1\\ &\sum_{d = 1}^n \mu(d) \frac{n}{kd} \frac{m}{kd}\\ \end{aligned}$$

然后直接对后面的数论分块就行了

题目

BZOJ1101: [POI2007]Zap

$\sum_{i = 1}^n \sum_{j = 1}^m gcd(i, j)$

按照套路，枚举$gcd$

$$\begin{aligned} &\sum_{d = 1}^n \sum_{i = 1}^n \sum_{j = 1}^m gcd(i, j) = d \\ &\text{后面的一坨直接按照第一种套路推，最终会得到}\\ &\sum_{d = 1}^n \sum_{k=1}^n \mu(k) \frac{n}{kd} \frac{m}{kd}\\ &\text{设$T = kd$}\\ &\sum_{T = 1}^n \frac{n}{T} \frac{m}{T} \sum_{d \ | T} d \mu(\frac{T}{d}) \end{aligned}$$

设$g(T) = \sum_{d \ | T} d \mu(\frac{T}{d})$

不难发现这是个严格的狄利克雷卷积的形式，那么显然$g$也是个积性函数，我们可以直接线性筛预处理后面的部分，数论分块搞前面的。总的复杂度就是$O(n + T\sqrt{n})$

拓展

这里题目最常见的拓展就是在$gcd(i, j)$外面再套一个函数，处理的策略都是一样的，化到最后得到的基本也都是积性函数，如果不是就暴力筛，是的话线性筛。至于怎么线性筛积性函数可以看这里。

题目

BZOJ4407: 于神之怒加强版

BZOJ4804: 欧拉心算

$\prod_{i = 1}^n \prod_{j = 1}^m gcd(i, j)$

$$\begin{aligned} &\prod_{d = 1}^n d^{{\sum_{i = 1}^n \sum_{j=1}^m} gcd(i, j) = d}\\ &\text{然后按照上面的套路推，可以得到下面的式子}\\ &\prod_{d = 1}^n d^{\sum_{k=1}^{\frac{n}{d}} \mu(k) \frac{n}{kd}\frac{m}{kd}}\\ &\text{设$T= kd$，枚举$T$}\\ &\prod_{T = 1}^n (\prod_{d \ | T} d^{\mu(\frac{T}{d})})^{\frac{n}{T} \frac{m}{T}}\\ \end{aligned}$$

设$g(T) = \prod_{d \ | T} d^{\mu(\frac{T}{d})}$

到了这里就有必要好好说说了，按照常规的套路反演出的$g(T)$应该是个积性函数，然而这里并不是，但是暴力打表之后可以发现一些规律

当$T$为质数的幂时, 设$T = p^q$，那么$g(T) = p$，除此之外$g(T) = 1$

那么直接枚举质数的幂次更新$g$，由于质数的密度大概是$\frac{n}{\ln n}$，而且每个质数的枚举上界为$\log n$那么总复杂度为$O(\frac{n}{ln n}) \log n = O(n)$

拓展

这种形式同样有许多的拓展，最常见的也是在$gcd$的那里再套上个什么函数

比如，[SDOI2017]数字表格就是要求

$$\sum_{i = 1}^n \sum_{j = 1}^m f(gcd(i, j))$$

其中$f(i)$表示第$i$个斐波那契数

这种题就按照套路推，推到最后一步，如果发现$g(T)$不能快速计算就直接暴力枚举因子，不然就xjb找规律。。

小结

莫比乌斯反演的一大特点就是套路性强，但是很多题还是相当有难度的，比如把某个问题转成反演，反演转图论。像我这种菜鸡肯定是这辈子都做不出来的qwq

参考资料

山东2017夏令营丁明朔讲课