浅谈莫比乌斯反演的常见套路
莫比乌斯反演的套路
emmm，因为我做过的题太少了，所以可能非常不全。
以下的式子都是用(\sum_{d \ | n} \mu(d) = n = 1)推出来的，想看"正规"形式的可以参考这里
如果不做特殊说明的话，(\frac{n}{k})默认为下取整，保证(n < m)
(\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}
然后直接对后面的数论分块就行了
题目
(\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))外面再套一个函数，处理的策略都是一样的，化到最后得到的基本也都是积性函数，如果不是就暴力筛，是的话线性筛。至于怎么线性筛积性函数可以看这里。
题目
(\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