莫比乌斯函数基础

莫比乌斯函数基础

这里只是浅要的谈一下莫比乌斯函数作为基础

定义

​ 我们通常使用 $\mu(x)$ 来表示，但莫比乌斯函数本身的实际意义并不明确。

$\mu(x)= \begin{cases} 1, & x=1 \\ (-1)^{k}, & {x=\prod_{i=1}^k}p_i \\ 0, & x=p^2 \cdots \end{cases}$

​ 说明一下，可能上述形式不太清楚：

​ 对于 $x=1$ 时，$\mu(x)=1$；

​ 考虑对 $x$ 质因数分解，如果存在平方因子形式，那么 $\mu(x)=0$；

​ 否则令质因子数为 $k$，那么 $\mu(x)=(-1)^k$。

​ 放一份线性求莫比乌斯函数的代码，原理类似求欧拉函数：

mu[1]=1;

vis[0]=vis[1]=true;

for(int i=2;i<=n;i++)
{
	if(!vis[i])
	{
		pri[++cnt]=i;
		mu[i]=-1;
	}
	for(int j=1;j<=cnt;j++)
	{
		if((lint)i*pri[j]>n) break;
		vis[i*pri[j]]=true;
		if(!(i%pri[j]))
		{
			mu[i*pri[j]]=0;
			break;
		}
	else mu[i*pri[j]]=-mu[i];
	}
}

一些基础的性质

​ 莫比乌斯函数是一个积性函数，即 $\mu(nm)=\mu(n)\mu(m)$，略证：

​ 如果 $\mu(x)=1$ 或者 $\mu(x)=0$，结果显然成立；

​ 当 $\gcd(n,m)=1$ 时，$\mu(nm)=(-1)^{\alpha_1+\alpha_2}$，而 $\mu(n)=(-1)^{\alpha_1},\mu(m)=(-1)^{\alpha_2}$，且 $n,m$ 没有相同的质因数，那么 $\mu(n,m)=\mu(n)\mu(m)$。

​ 且由此易知 $\mu(x)$ 并非完全积性函数，因为如果 $n,m$ 存在相同质因子，那么 $\mu(nm)=0$。

​ 设 $n$ 为正整数，那么有：

$\sum_{d|n}\mu(d)= \begin{cases} 1, & n=1 \\ 0, & n>1 \end{cases}$

​ 当 $n=1$ 时，原式显然为 $1$，那么现在考虑 $n>1$ 的情况。

​ 考虑算术基本定理易知：

$n=\prod_{i=1}^{k} {p_i}^{\alpha_i}$

​ 由于出现相同的质因子时 $\mu(x)=0$，对答案没有贡献，所以令 $m=\prod_{i=1}^{k} p_i$，易知：

$\sum_{d|n}\mu(d)=\sum_{d|m}\mu(d)$

​ 那么考虑到此时 $\mu(x)=(-1)^{k}$，与质因子的数量有关，那么枚举质因子的出现个数：

$\sum_{d|m}\mu(d)=\sum_{i=0}^{k}(-1)^{i}\binom{k}{i}$

​ 且由二项式定理易知，令 $x=1,y=-1$ 则有：

$\sum_{i=0}^{k}(-1)^{i}\binom{k}{i}=(x+y)^{k}=\Big(1+(-1)\Big)^{k}=0 \\ \sum_{d|n}\mu(d)=0$