Messy

莫比乌斯反演

Möbius 反演

(读这篇文章前,建议先使用容斥原理解决POJ3904)

现在假设我们要得到一种函数$\mu(d)$,这种函数具有以下性质:

$$ \begin{equation}f(n)= \sum_{d|n} \mu(d) = \begin{cases} 1, & n = 1 \\ 0, & n > 1 \end{cases} \end{equation} $$ 例如 $$ \begin{align*} f(1)&=\mu(1)=1\\ f(2)&=\mu(1)+\mu(2)=0\\ f(3)&=\mu(1)+\mu(3)=0\\ f(6)&=\mu(1)+\mu(2)+\mu(3)+\mu(6) =0\\ \end{align*} $$ 我们可以得到这个函数的前12个值:
m 1 2 3 4 5 6 7 8 9 10 11 12
\mu(m) 1 -1 -1 0 -1 1 -1 0 0 1 -1 0
Richard Dedekind 和 Joseph Liouville 发现了一个反演定理: $$ F(n)=\sum _{d|n}f(d)\Longleftrightarrow f(n)=\sum _{d|n}\mu(d)F(\frac{n}{d}) $$ 莫比乌斯函数: $$ \mu(n) = \begin{cases} 1, &n=1 \\ (-1)^k, & {n=p_1p_2...p_k, p_i互不相同} \\ 0, & \text{其它情况} \end{cases} $$