莫比乌斯函数
WorldBest丶牛顿
·
·
个人记录
写在前面
因为本人太蒻了，所以本文会有大量抄袭痕迹 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(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}
本处大量借鉴归纳（抄袭）了此博客的内容，有兴趣的可以去看看
莫比乌斯函数的特性
性质一
\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$ 的每个质因子指数为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$ 为积性函数，因此显然成立
### 性质三
$$\sum_{d|n}\frac{\mu(d)}{d}=\frac{\phi(n)}{n}
求出莫比乌斯函数
根据莫比乌斯函数的定义，我们可以通过调整欧拉筛，在线性的时间内求出 \mu
代码：
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
}
}
}
其实还有更快的方法求，需要使用杜教筛