莫比乌斯函数

2018-08-02 21:45:40


写在前面

因为本人太蒻了,所以本文会有大量抄袭痕迹 $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}$$

本处大量借鉴归纳(抄袭)此博客的内容,有兴趣的可以去看看



莫比乌斯函数的特性

性质一

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

代码:

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

其实还有更快的方法求,需要使用杜教筛