莫比乌斯反演

姓名: 陶荣杰
赛道: 提高组
类型: 算法技能

~~~~~~~~~~~~~~~~~~~~~~~~~ 莫比乌斯反演


前置知识:狄利克雷卷积,数论分块
  • 莫比乌斯函数
    ~~~~ 定义 \mu 为莫比乌斯函数,定义为
\mu(n)= \begin{cases} 0~~~~~~~~~~~~~n=1\\ 1~~~~~~~~~~~~~n含有平方因子\\ (-1)^k~~~~~k为n不同质因子个数 \end{cases} \tag{1}
  • 性质
\sum_{d|n}\mu(d)= \begin{cases} 1 ~~~~n=1\\ 0 ~~~~n\not=1 \end{cases}

~~~~~~~ 不难看出左边是 \mu 1 的狄利克雷卷积,而右边是元函数 \varepsilon ,所以 \mu * 1=\varepsilon

  • 补充结论

~~~~ 1.反演结论 [gcd(i,j)=1]=\sum_{d|gcd(i,j)}\mu(d)\tag{2}

~~~~~~ 证明:

[gcd(i,j)=1]=\varepsilon(gcd(i,j))= \\ (\mu * 1)(gcd(i,j))=\\ \sum_{d|gcd(i,j)}\mu(d)

~~~~ 2. \varphi(n)

\varphi(n)=\sum_{d|n}d\mu(\frac{n}{d}) \tag{3}

~~~~~~ 证明:
~~~ 学过狄利克雷卷积的人应该都知道(雾,有这么一个结论

\varphi*1=id

~~~ 我们不妨对左右两边同时卷 \mu 可得

\because~\varphi*1*\mu=id*\mu\\ \therefore~\varphi*(1*\mu)=id*\mu\\ \therefore~\varphi*\varepsilon=id*\mu\\ \therefore~\varphi=id*\mu\\ \therefore~ \varphi(n)=\sum_{d|n}id(d)\mu(\frac{n}{d})= \sum_{d|n}d\mu(\frac{n}{d})\\ (注意:此证明方法会在后面证明莫比乌斯反演用到)
  • 莫比乌斯函数与线性筛
    ~~~~ 由于 \mu 是积性函数,我们可以根据他的性质用线性筛求出莫比乌斯函数
void Muelsyse(){
	vis[1]=mu[1]=1;
	for(int i=2;i<=N;i++){
		if(!vis[i]) prime[++cnt]=i,mu[i]=-1;
		for(int j=1;j<=cnt&&i*prime[j]<=N;j++){
			vis[i*prime[j]]=1;
			if(i%prime[j]==0){
				mu[i*prime[j]]=0;
				break;
			}	
			mu[i*prime[j]]=-mu[i];
		}
	}
}
  • 莫比乌斯变换( and 反演)
    ~~~~ f(n),g(n) 是两个数论函数。
    ~~~~ 形式一:如果 f(n)=\sum\limits_{d|n}g(d), 那么 g(n)=\sum\limits_{d|n}\mu(d)f(\frac{n}{d})。
    ~~~~ 形式二:如果 f(n)=\sum\limits_{n|d}g(d), 那么 g(n)=\sum\limits_{n|d}\mu(\frac{d}{n})f(d)。
    这种形式下,数论函数 f(n) 称为数论函数 g(n) 的莫比乌斯变换,数论函数 g(n) 称为数论函数 f(n) 的莫比乌斯逆变换(反演)。
    容易看出,数论函数 g(n) 的莫比乌斯变换,就是将数论函数 g(n) 与常数函数 1 进行狄利克雷卷积。

~~~~~~ 证明:(运用狄利克雷卷积)

~~~~~ 原命题:已知 f=g*1, 求证 g=f*\mu
~~~~~ f=g*1 左右两边同时卷 \mu

g*1*\mu=f*\mu\\ g*(1*\mu)=f*\mu\\ g*\varepsilon=f*\mu\\ g=f*\mu
  • 例题
求 \sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)==k]的值

先改变枚举上限

\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[gcd(i,j)==1]

使用反演结论

\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}\sum_{d|gcd(i,j)}\mu(d)

改变求和顺序先枚举 {d|gcd(i,j)}

\sum_{d=1}^{min(\lfloor\frac{n}{k}\rfloor,\lfloor\frac{m}{k}\rfloor)}\mu(d)\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}[d|i]\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[d|j]

我们知道 1 ~ \lfloor\frac{n}{k}\rfloor d 的倍数有 \lfloor\frac{\lfloor\frac{n}{k}\rfloor}{d}\rfloor 个,也就是 \lfloor\frac{n}{kd}\rfloor 个 原式便能转换为

\sum_{d=1}^{min(\lfloor\frac{n}{k}\rfloor,\lfloor\frac{m}{k}\rfloor)}\mu(d)\lfloor\frac{n}{kd}\rfloor\lfloor\frac{m}{kd}\rfloor

显然使用数论分块

~~~~ more题:
~~~~ Crash的数字表格 / JZPTAB
~~~~ [HAOI2011] Problem b

特别感谢:@潘建希
喜欢的记得点个赞,Ciallo~(∠・ω< )⌒☆

6 个赞

老总结了,最近在写树剖

1 个赞

@陶荣杰1 莫反是省选的
image

1 个赞

没关系,提高可学(doge