莫比乌斯反演习题总结

2023-12-10 20:28:10

一：常用卷积

\[1 * \mu = \epsilon\]

\[Id * \mu = \varphi\]

\[1 * \varphi = Id \]

最后一个是欧拉反演.

根据这些卷积之间的相互转化，在推式子时只要够敏感，就能巧妙地化简。（如P3768简单的数学题）

二：推式子的技巧

1. 改变枚举对象、枚举顺序

比如
\[ \begin{aligned} 1. &\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)=p]\\ =&\sum_{x=1}^{\frac{n}{p}}\sum_{y=1}^{\frac{n}{p}}[gcd(i,j)=1]\\ 2.&\sum_{i=1}^{n}\sum_{j=1}^ngcd(i,j)\\ =&\sum_{d=1}^{n}d\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}}[gcd(i,j)=1] \end{aligned} \]

当一个一个数不受之前的 \(\sum\) 限制时可提前

2. 替换变量，优化复杂度(式子中不必要的枚举)

比如求这个：

\[ \begin{aligned} &\sum_{k=1}^nk\sum_{d=1}^\frac{n}{k}\mu(d)\frac{n}{dk}\frac{m}{dk}\\ =&\sum_{T=1}^n\frac{n}{T}\frac{m}{T}\sum_{d|T}\frac{T}{d}\mu(d) \end{aligned} \]

为什么这样？

其实替换变量也是为了改变枚举顺序，然后就可以愉快地整除分块了。