莫比乌斯反演总结

标签：总结

1.序

做了一段时间的莫比乌斯反演题目，决定还是总结一下莫比乌斯反演做题方法（套路）吧。便于以后的复习与理解

2.莫比乌斯函数

莫比乌斯函数本质是一个容斥函数，它的定义如下:
当$d=1$时$u(d)=1$
当$d=\prod_{i=1}^{n}pi$时$u(d)=(-1)^n$（pi为质数）
当d的任何一个质因子次数>1,$u(d)=0$
通俗意思就是当d质因数分解以后，所有的质因子次数都为1的话，那么$u(d)=(-1)^{n}$（n为质因数个数，d=1可以理解为质因数为0）

3.莫比乌斯反演

定理：在非负整数域上存在两个函数$F(n)$和$f(n)$，并且满足以下条件：
$$F(n)=\sum_{d|n}f(d)$$
则
$$f(n)=\sum_{d|n}u(d)F(\frac{n}{d})$$
以下给出一个简单的证明:
$$\sum_{d|n}u(d)F(\frac{n}{d})=\sum_{d|n}u(d)\sum_{i|\frac{n}{d}}f(i)=\sum_{i|n}f(i)\sum_{d|\frac{n}{i}}u(d)=f(n)$$
第一个等式利用第一直接变换
第二个等式是枚举项的转换，因为两个等式其实就等价于这个：
$$\sum_{(i*d)|n}f(i)u(d)$$
可以自己举一个栗子更好理解，比如n=12的时候
第三个等式就是利用莫比乌斯函数的第一条性质
当然，在做题的时候我们更倾向于用下列式子：
$$F(n)=\sum_{n|d}f(d)$$
$$f(n)=\sum_{n|d}u(\frac{d}{n})F(d)$$
这个证明的话需要用狄利克雷卷积，直观理解就是一个为枚举约数，一个枚举倍数

4.等式变换技巧

想要做莫比乌斯反演的题目，一般都是需要对原式子进行和式的变换，然后再开始反演；或者是先设$f(x)$和$F(x)$函数对原式反演后在进行和式的变换

1.求和式子中的位置变换

对于求和式多项式中一些与枚举无关的变量可以提前：
$$\sum_{i=1}^{n}\sum_{j=1}^{m}f(i)g(j)=\sum_{i=1}^{n}f(i)\sum_{j=1}^{m}g(j)$$

2.更改枚举项

有时候在化简的时更改枚举项会使得和式变得更简单：
比如我们求以下式子:
$$\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|gcd(i,j)}d$$
我们可以更改枚举项在外层枚举$gcd(i,j)$
$$Ans=\sum_{d=1}^{min(n,m)}d\sum_{i=1}^{n}\sum_{j=1}^{m}[d|gcd(i,j)]$$
对于后面那一坨式子，我们又可以考虑枚举d的倍数：
$$\sum_{i=1}^{n}\sum_{j=1}^{m}[d|gcd(i,j)]=\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}[1|gcd(i,j)]$$
对于$1|gcd(i,j)$对于每个gcd肯定都能满足，所以最终我们化简为：
$$\sum_{i=1}^{min(n,m)}d\left \lfloor \frac{n}{d} \right \rfloor\left \lfloor \frac{m}{d} \right \rfloor$$
对于枚举项的更改，我们一般是考虑枚举gcd，枚举一个数的倍数，或者替换一些繁琐的未知数，例如：

$$Ans=\sum_{d=1}^{n}\sum_{p=1}^{m}d*u(p)\left \lfloor \frac{n}{dp} \right \rfloor\left \lfloor \frac{m}{dp} \right \rfloor$$

诸如有两个或多个变量在一起的时候我们可以考虑替换这些变量，对于上述这个式子我们设$T=dp$,则

$$Ans=\sum_{d=1}^{n}\sum_{p=1}^{m}d*u(p)\left \lfloor \frac{n}{T} \right \rfloor\left \lfloor \frac{m}{T} \right \rfloor$$

可以发现此时我们如果把T看成一个独立变量，那么它与$d,p$都无关了，于是我们考虑枚举T：
$$\sum_{T=1}^{upper\cdot bound}\frac{n}{T}\frac{m}{T}\sum_{d|T}d\ast u(\frac{T}{d})$$
机智的童鞋可以发现后面的和式利用莫比乌斯函数性质能再次化简呢:
$$\sum_{d|T}d\ast u(\frac{T}{d})=\sum_{d|T}\frac{T}{d}\ast u(d)=\frac{1}{T}\sum_{d|T}\frac{u(d)}{d}=\varphi (T)$$
不过在更改枚举项的时候，一定要注意对其他变量的贡献产生了影响，比如：
$$\sum_{i=1}^{n}\sum_{j=1}^{m}ij[gcd(i,j)==d]$$
考虑更改枚举d的倍数
$$\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}(i\ast d)(j\ast d)[gcd(i,j)==1]$$
此时的$i,j$需要变成$i\ast d,j\ast d$ 因为我们的i，j变成了枚举d的倍数

3.对$gcd(i,j)==1$的替换

$$gcd(i,j)==1 <=> \sum_{d|gcd(i,j)}u(d)$$
证明利用莫比乌斯函数性质即可。

5.整除分块

对于一段区间$[l,r]$，对于一个数n，总会存在一段区间使得$\left \lfloor \frac{n}{l} \right \rfloor=\left \lfloor \frac{n}{r} \right \rfloor=k$ 那么对于诸如求下列式子:$\sum_{i=1}^{n}f(\left \lfloor \frac{n}{i} \right \rfloor)$我们就可以把它分割成一小段一小段的区间求解于是便优化了时间复杂度，其中$r=\frac{n}{\left \lfloor \frac{n}{l} \right \rfloor}$证明的话…博客靠的是感性的理解~~