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 |