莫比乌斯反演
定义
先讲讲莫比乌斯函数的定义：
\(\mu(x) =\begin{cases} 1 &n=1 \\ 0 &n含有平方因子 \\ (-1)^k &k为n的本质不同质因子个数 \end{cases}\)
我们对 \(n\) 进行质因数分解，
\(n= \prod_{i=1}^k p_i^{c_i}\)，其中 \(p_i\) 是质因子，而 \(c_i \ge 1\).
-
\(n=1\)，\(\mu(n)=1\)，显然这是积性函数都有的性质
-
\(n \ne 1\)，
- 若存在 \(i\in [1,k]\)，使得 \(c_i>1\)，那么 \(\mu(n)=0\)，平方因子就是次数为 \(2\) 的质因子。若 \(c_i=2\) , 没什么好说的。若 \(c_i>2\) ，可以化成 \(p_i \times p_i^2\) 的形式。
- 若不存在 \(i\in [1,k]\)，使得 \(c_i>1\)，那么 \(\mu(n)=(-1)^k\)