莫比乌斯反演

（读这篇文章前，建议先使用容斥原理解决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个值：

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}
$$