莫比乌斯反演专题学习笔记

本文记录一些和莫反有关的内容的笔记

可能存在诸多谬误，阅读时请谨慎分析

若发现文中有谬误，如您愿意，恳请您向我指出，不胜感激！

为什么要学莫比乌斯反演？

解决一类与狄利克雷卷积、整除、积性函数有关的问题，通过莫比乌斯反演，往往可以将复杂度优化到可接受的范围内

积性函数

对于任意互质整数a,ba,b有f(ab)=f(a)f(b)f(ab)=f(a)f(b)的函数称为积性函数

对于任意整数a,ba,b有f(ab)=f(a)f(b)f(ab)=f(a)f(b)的函数称为完全积性函数

常见，重要的积性函数有：

欧拉函数φ(n)\varphi(n)
莫比乌斯函数μ(n)\mu(n)
狄利克雷卷积单位元ε=[n=1]\varepsilon=[n=1]
不变函数1(n)=1{\bf{1}}(n)=1

狄利克雷卷积

函数f,gf,g的狄利克雷卷积(f∗g)(f*g)定义如下

(f∗g)(n)=∑d∣nf(nd)g(d)(f*g)(n)=\sum_{d|n}f(\frac{n}{d})g(d)

狄利克雷卷积的单位元为ε=[n=1]\varepsilon=[n=1]（把它代入到狄利克雷卷积中，可以发现f∗ε=ff*\varepsilon=f）

莫比乌斯函数

莫比乌斯函数定义如下：

μ(i)={1,if i = 1(−1)k,if i=p1p2p3…pk(p∈prime)0,otherwise\mu(i)=\begin{cases}1,& \text{if i = 1}\\(-1)^k,& \text{if i=}p_1p_2p_3\dots p_k(p\in prime)\\0,&\text{otherwise}\end{cases}

下面证明莫比乌斯函数的狄利克雷卷积逆是不变函数，即

μ∗1=ε\mu*{\bf{1}}=\varepsilon

以下过程引自【算法讲堂】【电子科技大学】【ACM】莫比乌斯反演

证明：设nn的不同质因子的个数为kk，则有

μ∗1=∑d∣nμ(d)=∑i=0k(−1)i(ki)\mu*{\bf{1}}=\sum_{d|n}\mu(d)=\sum_{i=0}^k(-1)^i\begin{pmatrix}k\\i\end{pmatrix}

由二项式定理，有

(x+y)k=∑i=0kxiyk−i(ki)(x+y)^k=\sum_{i=0}^kx^iy^{k-i}\begin{pmatrix}k\\i\end{pmatrix}

令x=−1,y=1x=-1,y=1代入得

0k=∑i=0k(−1)i(ki)0^k=\sum_{i=0}^k(-1)^i\begin{pmatrix}k\\i\end{pmatrix}

即

μ∗1=ε\mu*{\bf{1}}=\varepsilon

证毕

由此，我们得到莫比乌斯函数的一个性质∑d∣mμ(d)=[m=1]\sum_{d|m}\mu(d)=[m=1]

由于莫比乌斯函数具有积性，我们可以用线性筛来求出莫比乌斯函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void GetPrime()
{
	nop[1]=1,mu[1]=1;
	for(register int i=2;i<=N;++i)
	{
		if(!nop[i])pri[++pcnt]=i,mu[i]=-1; 
		for(register int j=1;j<=pcnt && i*pri[j]<=N;++j)
		{
			nop[i*pri[j]]=1;
			if(i%pri[j]==0)break;
			else mu[i*pri[j]]=-mu[i];
		}
	}
}

莫比乌斯反演

  • g(n)=∑d∣nf(d)→f(n)=∑d∣nμ(d)g(nd)g(n)=\sum_{d|n}f(d)\rightarrow f(n)=\sum_{d|n}\mu(d)g(\frac{n}{d})

证明：

g=f∗1,μ∗g=f∗1∗μ=fg=f*{\bf{1}},\mu*g=f*{\bf{1}}*\mu=f

证毕

  • g(n)=∑n∣df(d)→f(n)=∑n∣dμ(dn)g(d)g(n)=\sum_{n|d}f(d)\rightarrow f(n)=\sum_{n|d}\mu(\frac{d}{n})g(d)

证明略

整除分块

整除分块可以以O(n)O(\sqrt n)的复杂度计算∑i=1n⌊ni⌋\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor

首先我们发现⌊ni⌋\lfloor\frac{n}{i}\rfloor至多只有2n\sqrt{2n}个取值，并且每个取值都是一段连续的“块”

对于每一块[l,r][l,r]，∀i∈[l,r]\forall i\in[l,r]有⌊ni⌋=⌊nl⌋\lfloor\frac{n}{i}\rfloor=\lfloor\frac{n}{l}\rfloor

并且，r=n/(n/l)r=n/(n/l)

我们只需要逐段计算即可

有时候，我们推出的式子可能还需要乘上一个函数，如φ,μ\varphi,\mu等，这时候我们只需要先对函数求前缀和，每次计算一段时乘上这一段对应的函数之和即可

1
2
3
4
5
6
for(int l=1,r;l<=n;l=r+1)
{
    r=n/(n/l);
    re+=(r-l+1)*(n/l);
//  re+=(sum[r]-sum[l-1])*(n/l);
}

参考资料

【算法讲堂】【电子科技大学】【ACM】莫比乌斯反演https://www.bilibili.com/video/av43470417