数学知识

莫比乌斯反演 设F(n)和f(n)为定义在非负整数集合上的函数，令F(n)=∑d|nf(d)$F(n)=/sum_{d|n} {f(d)}$,则有结论： f(n)=∑d|nμ(d)F(nd)$f(n)=/sum_{d|n}{/mu(d)F(/frac{n}{d})}$ 函数μ的定义如下： （1）若d=1，那么 μ(d)=1$/mu(d)=1$; （2）若d=p1∗p2∗…∗pk$d=p1*p2*…*pk$，pi均为互异素数，那么μ(d)=(−1)k$/mu(d)=(-1)^k$; （3）其它情况下μ(d)=0$/mu(d)=0$;

对于函数，它有如下的常见性质： （1）对任意正整数有 （2）对任意正整数有 证明:∑d|nμ(d)F(nd)=∑d|nμ(d)∗∑d′|ndf(d′)=∑d′|nf(d′)∑d|nd′=f(n)$/sum_{d|n}{/mu(d)F(/frac{n}{d})}=/sum_{d|n}{/mu(d)}*/sum_{d'|/frac{n}{d}}{f(d')}=/sum_{d'|n}{f(d')}{/sum_{d|/frac{n}{d'}}}=f(n)$