Dirichlet卷积和莫比乌斯反演

非全面讲解，仅供记录笔记

Dirichlet卷积

\[(f\ast g)(n)=\sum_{d\mid n}f(d)g(\frac{n}{d})\] \[\varepsilon =\mu \ast 1 \iff \varepsilon(n) = \sum_{d\mid n} \mu(d)\] 其中\(\varepsilon\)卷任何函数等于其函数本身。

莫比乌斯函数\(\mu\)

定义

\[\mu(n)=\begin{cases}1&n=0\\(-1)^k&k为n的本质不同质因子个数\\0&otherwise\\ \end{cases}\]

性质

• \[\sum_{d\mid n}\mu(d)=\begin{cases}1&n=1\\0&n\neq 1\\ \end{cases}\\]
• 积性函数，所以可以线性筛求得：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

inline void getMu(){
	mu[1]=1;
	for(int i=2;i<=maxn;i++){
		if(!mark[i])prime[++tot]=i,mu[i]=-1;
		for(int j=1;j<=tot and i*prime[j]<=maxn;j++){
			mark[i*prime[j]]=1;
			if(i%prime[j]==0){
				mu[i*prime[j]]=0;
				break;
			}
			mu[i*prime[j]]=-mu[i];
		}
	}
}

莫比乌斯反演

若有 \[f(n) = \sum_{d\mid n}g(d)\]

则有

\[g(n)=\sum_{d\mid n}\mu(\frac{d}{n})f(d)\]

正确性证明（卷积）：

原问题即已知 \(f=g*1\) 求证 \(g=f*\mu\)

证明：\(f*\mu=g*1*\mu \implies f*\mu = g*\varepsilon \implies f*\mu=g\)

得证。

反演结论

\[[\gcd(i,j)=1]\iff\sum_{d\mid\gcd(i,j)}\mu(d)\]

例题

P2522 Problem b

容斥原理，分别求四个从1开始的区间的个数合并即可。

那么我们的问题就是处理单个区间的个数。

求 \[\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=k]\] 即 \[\sum_{i=1}^{\frac{n}{k}}\sum_{j=1}^{\frac{m}{k}}[\gcd(i,j)=1]\] 即 \[\sum_{i=1}^{\frac{n}{k}}\sum_{j=1}^{\frac{m}{k}}\sum_{d\mid \gcd(i,j)}\mu(d)\] 即 \[\sum_{d=1}^{min(\frac{n}{k},\frac{m}{k})}\mu(d)\lfloor\frac{n}{kd}\rfloor\lfloor\frac{m}{kd}\rfloor\] 然后数论分块求即可。