莫比乌斯反演

未分类

---

莫比乌斯反演

对于函数$f(n)$和$g(n)$,如果有$f(n)=\sum_{d|n}g(d)$,那么有$g(n)=\sum_{d|n}\mu(d)f(n/d)$.
$PS.$下面用到的$\phi(n)$是指欧拉函数,$\mu(n)$是指莫比乌斯函数.
由此得到的几个结论:

$$n=\sum_{d|n}\phi(d),\phi(n)=\sum_{d|n}\mu(d)(n/d)$$
$$[n==1]=\sum_{d|n}\mu(d),\mu(n)=\sum_{d|n}\mu(d)[n/d==1]$$

狄利克雷卷积$(f*g)(n)=\sum_{d|n}f(d)g(n/d)$

$$\begin{align*} \phi(n) &=\sum_{d|n}\mu(d)(n/d) \\ &= \sum_{d|n}\mu(d)\sum_{d'|n/d}\phi(d') \\ &= \sum_{dd'|n}\mu(d)\phi(d') \\ &= \sum_{d|n}\sum_{d'|d}\mu(d')\phi(d/d') \\ &= \sum_{d|n} (\mu*\phi)(d) \end{align*}$$

实际上对于所有满足反演条件的$f$都有$f(n)=\sum_{d|n}(\mu*f)(d)$

杜教筛
求$s(n)=\sum_{i=1}^nf(n)$.
选一个函数$g$和$f$做狄利克雷卷积:

$$\begin{align*} (f*g)(n)&=\sum_{d|n}f(d)g(n/d) \\ \sum_{i=1}^n(f*g)(i) &= \sum_{i=1}^n\sum_{d|i}f(d)g(i/d) \\ &= \sum_{d=1}^ng(d)\sum_{i=1}^{\lfloor n/d\rfloor}f(i) \\ &= \sum_{d=1}^ng(d)s(\lfloor n/d \rfloor) \\ &= \sum_{d=2}^ng(d)s(\lfloor n/d \rfloor)+g(1)s(n) \\ g(1)s(n) &=\sum_{i=1}^n(f*g)(i)-\sum_{d=2}^ng(d)s(n/d) \end{align*}$$
选取一个合适的$g$和$f$做狄利克雷卷积,使$(f*g)(n)$的前缀和是易求的,就可以通过数论分块来解决求和问题,通过预处理$s$的前$n^{\frac{2}{3}}$项,可以在$O(n^{\frac{2}{3}})$的时间求解该问题.