莫比乌斯函数

# 写在前面 因为本人太蒻了，所以本文会有大量抄袭痕迹 $qwq$ ~~如有雷同，确实就是我抄的~~ **来源见最后** # 定理 设 $F(x)$ 与 $f(x)$ 是定义在 $N^* $ 上的两个函数 满足 $$F(n)=\sum_{d|n}f(d)$$ 则有 $$f(n)=\sum_{d|n}\mu(d)f(\frac{n}{d})$$ 其中 $μ(d)$ 为莫比乌斯函数 ------------ ------------ # 莫比乌斯函数 由前提条件 $$F(n)=\sum_{d|n}f(d)$$ 我们可知 $$\begin{cases} F(1)=f(1) \\ F(2)=f(1)+f(2) \\ F(3)=f(1)+f(3) \\ F(4)=f(1)+f(2)+f(4) \\ F(5)=f(1)+f(5) \\ F(6)=f(1)+f(2)+f(3)+f(6) \\ F(7)=f(1)+f(7) \\ F(8)=f(1)+f(2)+f(4)+f(8) \end{cases}$$ $$\Downarrow$$ $$\begin{cases} f(1)=F(1) \\ f(2)=F(2)-F(1) \\ f(3)=F(3)-F(1) \\ f(4)=F(4)-F(2) \\ f(5)=F(5)-F(1) \\ f(6)=F(6)-F(3)-F(2)+F(1) \\ f(7)=F(7)-F(1) \\ f(8)=F(8)-F(4) \end{cases}$$ 我们可以发现，从 $F$ 逆向推 $f(n)$ 时，只需将与 $f(n)$ 有关的 $F$ 进行容斥 但是每个 $F(x)$ 的系数怎么确定呢？ 我们设 $G(d,n)$ 表示求解$ F(n)$ 时， $f(d)$ 的系数 以 $F(6)$ 为例，可以得到这个式子 $$f(6)=G(6,6)* F(6)+G(2,6)* F(2)+G(3,6)* F(3)+G(1,6)* F(1)$$ 我们将每个 $G$ 分别用 $a,b,c,d$ 代换，用含 $f$ 的式子代入 $F$ $$f(6)=a* (f(6)+f(3)+f(2)+f(1))+b* (f(2)+f(1))+c* (f(3)+f(1))+d* f(1)$$ 移项，合并同类项，得到 $$f(6)* (a-1)+f(3)* (a+c)+f(2)* (a+b)+f(1)* (a+ b+c+d)=0$$ 将$ f(6),f(3),f(2),f(1) $看做不同的元，可以得到系数方程组 $$\begin{cases} a-1=0 \\ a+c=0 \\ a+b=0 \\ a+b+c+d=0 \end{cases}$$ 由此发现，只需要解出方程，就能知道对于 $F$ 的系数 那么对于每个 $ f(n) $ ,假设他的因子数为 $ m $ ，则通过这种方式，总能设出 $ m $ 个未知数，$ m $ 个方程，而这 $ m $ 个方程一定是有解的 ------------ 对于 $G$ ，我们可以证明一个结论 $$G(a,b)=G(1,\frac{b}{a})$$ **(温馨提示：以下需要强大的心算~~(YY)~~能力，想不通的话可以拿出纸笔或者打开 附件—画图 )** 以求解 $f(8)$ 为例，则有 $$f(8)=G(8,8)* F(8)+G(4,8)* F(4)+G(2,8)* F(2)+G(1,8)* F(1)$$ $$f(8)=G(8,8)* (f(1)+f(2)+f(4)+f(8))+G(4,8)* (f(1)+f(2)+f(4))+G(2,8)* (f(1)+f(2))+G(1,8)* f(1)$$ 首先 $G(8,8)$ 的值可以直接确定，因为把 $f(8)$ 当作元的话，左边一个 $f(8)$ ,而在右边 $f(8)$ 只在 $F(8)$ 中出现，所以 $G(8,8)=1$ 同理，对于 $\forall f(n)$ ，其 $F(n)$ 的系数 $G(n,n)=1$ ，所以 $G(8,8)=G(1,1)$ 再看 $G(4,8)$ ,发现 $f(4)$ 在 $F(8)$ 和 $F(4)$ 出现，因为左边不含 $f(4)$ ，而前面 $F(8)$ 的系数又已经确定，所以这里 $G(4,8)* F(4)$ 的作用就是为了抵消前面 $F(8)$ 的代换中出现的$f(4)$，所以 $G(4,8)=-G(8,8)=-G(2,2)=G(1,2)$ ($G(1,2)=-G(1,1)$留给读者自证(o(*////▽////*)q) 同理，对于 $G(2,8)$ ，他是为了抵消前面在 $F(8)$ 和 $F(4)$ 中出现的 $f(2)$ ，所以 $G(2,8)$ 相当于受到 $G(4,4)$ 和 $G(2,4)$ 的影响（假设这个结论对 $n=4$ 也成立，$G(2,4)=G(1,2)$）， 所以 $G(2,8)=G(1,4)$ 总结一下，假设 $n$ 的因子有 $d_1,d_2,d_3 \dots ,d_m$ 其中 $d_1>d_2>d_3 \dots >d_m$ 我们依次确定 $G(d_i,n)$ 的值，当我们在确定 $G(d_i,n)$ 的值时，前面的值已经确定，即 $G(d_j,n)(j<i)$ 的值已经确定， $G(d_i,n)$ 会受到前面一些 $G(d_j,n)$ 的影响，当且仅当 $d_j>d_i$ 且 $d_i|d_j$ 。 假设 $G(a,b)=G(1,\frac{b}{a})$ 对前面的 $G(d_j,n)$ 和所有的 $G(k,m)$ 其中 $m<n$ 已经成立(首先对于 $G(n,n)$ 已经成立)，那么有 $$G(d_j,n)=G(1,\frac{n}{d_j})=G(\frac{d_j}{d_i},\frac{n}{d_i})$$ 这样就把前面对 $G(d_i,n)$ 造成影响的 $G$ 由 $G(d_j,n)$ 转为了 $G(\frac{d_j}{d_i},\frac{n}{d_i})$ ,所以$G(d_i,n)$ = $G(1,\frac{n}{d_i})$ 既然 $G(a,b)$ 可以写成 $G(1,\frac{b}{a})$，那么我们就可以把 $G$ 的第一个元素省略，简写为 $G(n)$ 说到这里，就可以把 $G$ 和 $\mu$ 联系起来了，其实 $$\mu(n)=G(n)= G(1,n)$$ 于是，我们就可以给 $\mu(n)$ 赋予一个更具体的意义： $\mu(n)$ 表示在计算 $f(n)$ 时，$F(1)$的系数！！(因为 $\mu(n)=G(1,n)$ ) ------------ 首先需要明确2点！ 一、$F(n)$ 中,一定包含一个 $f(1)$，因为 $1|n$ 二、$f(1)=F(1)$ 下面开始推理： （1） 如果 $n=1$ ，因为 $f(1)=F(1)$，所以 $$\mu(1)=1$$ ------------ （2） 假设 $n$ 是一个质数 $$f(n)=\mu(1)* F(n)+\mu(n)* F(1)$$ 代入 $\mu(1)=1$ , 因为 $F(n)$ 中含有一个 $f(1)$ ，而左边不含 $f(1)$ ，所以我们需要利用 $F(1)$ 来消去 $f(1)$ 所以 $$\mu(n)=-1$$ （3） 假设 $n$ 可以写成两个不同质数的乘积 $n=pq$ 那么 $$f(n)=\mu(1)* F(pq)+\mu(q)* F(p)+\mu(p)* F(q)+\mu(n)* F(1)$$ 这里 $\mu(1)$，$\mu(p)$，$\mu(q)$ 就是前面两种情况 代入系数，因为左边没有 $f(1)$，所以为了抵消右边的 $f(1)$ ，我们需要令 $$\mu(n)=1$$ （4） 假设 $x$ 可以写成三个不同质数的乘积 $x=p*p1*p2$ 我们令 $z=p1*p2$ $$f(n)=\mu(1)* F(pz)+\mu(z)* F(p)+\mu(p)* F(z)+\mu(n)* F(1)$$ 其中 $\mu(1),\mu(p),\mu(z)$ 分别为前面三种情况，代入过后 ，为抵消 $f(1)$ 得到 $$\mu(n)=-1$$ 由此可以相同的方式向下递推，得到**第一条结论** 如果 $n=p_1p_2\cdots p_k$ , 其中$p_i$是互异的质数，那么 $$\mu(n)=(-1)^k$$ ------------ （5） 假设 $n$ 可以写成一个质数的平方 $n=p^2$ $$f(n)=\mu(1)* F(n)+\mu(p)* F(p)+\mu(n)*F (1)$$ 代入系数，得到 $$\mu(n)=0$$ （6） 假设 $n$ 可以写成一个质数的三次方 $n=p^3$ $$f(n)=\mu(1)* F(n)+\mu(p)* F(p^2)+\mu(p^2)* F(p)+\mu(n)* F(1)$$ 代入系数后 $$\mu(n)=0$$ 由此可用相同方式向下递推，得到**第二条结论** 如果 $n=p^k(k>1)$ $$\mu(n)=0$$ （7） 假设 $n$ 可写成 $n=p^k* q$ 其中 $p,q$ 为不同质数，$k>1$ $$f(n)=\mu(1)* F(n)+\mu(q)* F(p^k)+\mu(p^k)* F(q)+\mu(n)* F(1)$$ 代入系数后 $\mu(n)=0$ 由此可继续向下递推，得到**第二条结论的加强版** 如果 $n=p^kz$，其中 $p$ 为质数， $z$ 为任意数， $k>1$ ，那么 $$\mu(n)=0$$ ------------ ### 总结： $$\mu(n)=\begin{cases} 1\qquad ,n=1 \\ (-1)^k,n=p_1p_2p_3\cdots p_k \\ 0\qquad ,n=p^kz(k>1) \end{cases}$$ 本处大量借鉴归纳~~（抄袭）~~了[此博客](https://www.cnblogs.com/chenyang920/p/4811995.html)的内容，有兴趣的可以去看看 ------------ ------------ # 莫比乌斯函数的特性 ### 性质一 $$\sum_{d|n}\mu(d)=[n==1]$$ 其中 $[n==1]$ 为布尔型，即条件为 $true$ 时值为 $1$ ，为 $false$ 时值为 $0$ 证明： ① $n=1$，显然成立 ② $n>1$, 设 $n=p_1^{k1}p_2^{k2}p_3^{k3}\cdots p_m^{km}$ $d$ 有其中一部分 ∴ $d$ 的每个质因子指数为1时才有贡献，否则 $\mu(d)=0$ 设 $d$ 中有 $r$ 个质因子 $\mu(d)=(-1)^r$，这样的 $d=C_m^r$ 根据二项式定理可得 $$\sum_{r=0}^{m}(-1)^rC_m^r=\sum_{r=0}^{m}C_m^r(-1)^r* 1^{m-r}=(-1+1)^m=0$$ ### 性质二 $$\text{若}(p,q)=1$$ $$\mu(p)* \mu(q)=\mu(p* q)$ 因 $\mu$ 为积性函数，因此显然成立 ### 性质三 $$\sum_{d|n}\frac{\mu(d)}{d}=\frac{\phi(n)}{n}$$ ------------ ------------ # 求出莫比乌斯函数 根据莫比乌斯函数的定义，我们可以通过调整欧拉筛，在线性的时间内求出 $\mu$ 代码： ```cpp void make_miu(int n)//求出从1到n的μ值 { miu[1]=1; for(int i=2;i<=n;++i)//欧拉筛 { if(!vis[i]) { miu[i]=-1;//i为质数，则μ[i]=-1 prime[++cnt]=i; } for(int j=1;j<=cnt&&prime[j]*i<=n;++j) { vis[prime[j]*i]=true; if(i%prime[j]==0) break; else miu[prime[j]*i]=-miu[i]; //目前prime[j]*i的质因子为j的质因子数+1 } } } ``` 其实还有更快的方法求，需要使用杜教筛