莫比乌斯反演是数论中的重要内容,对于一些函数 f(n) ,如果很难直接求出它的值,而容易求出其倍数和或约数和 g(n) ,那么可以通过莫比乌斯反演简化运算,求得 f(n) 的值。
开始学习莫比乌斯反演前我们需要一些前置知识:积性函数、Dirichlet卷积、莫比乌斯函数
数论分块与整除相
引理 1
∀a,b,c∈Z,⌊abc⌋=⌊⌊ab⌋c⌋略证
ab=⌊ab⌋+r(0≤r<1)⇒⌊abc⌋=⌊ab⋅1c⌋=⌊1c(⌊ab⌋+r)⌋=⌊⌊ab⌋c+rc⌋=⌊⌊ab⌋c⌋引理 2
∀n∈N,∣{⌊nd⌋∣d∈N}∣≤⌊2√n⌋∣V∣ 表示集合 V 的元素个数
略证
对于 d≤⌊√n⌋ , ⌊nd⌋ 有 ⌊√n⌋ 种取值
对于 d>⌊√n⌋ ,有 ⌊nd⌋≤⌊√n⌋ ,也只有 ⌊√n⌋ 种取值
综上得证
数论分块
数论分块的过程大概如下:考虑含有 ⌊ni⌋ 的求和式子( n 为常数)
对于任意一个 i(i≤n) ,我们需要找到一个最大的 j(i≤j≤n) ,使得 ⌊ni⌋=⌊nj⌋
而 j=⌊n⌊ni⌋⌋
略证
⌊ni⌋≤ni⇒⌊n⌊ni⌋⌋≥⌊nni⌋=⌊i⌋=i⇒i≤⌊n⌊ni⌋⌋即 j=⌊n⌊ni⌋⌋
利用上述结论,我们每次以 [i,j] 为一块,分块求和即可
积性函数
定义
若 gcd(x,y)=1 且 f(xy)=f(x)f(y) ,则 f(n) 为积性函数。
性质
若 f(x) 和 g(x) 均为积性函数,则以下函数也为积性函数
h(x)=f(xp)h(x)=fp(x)h(x)=f(x)g(x)h(x)=∑d∣xf(d)g(xd)例子
- 单位函数: ϵ(n)=[n=1]
- 恒等函数: idk(n)=nkid1(n) 通常记做 id(n)
- 常数函数: 1(n)=1
- 除数函数: σk(n)=∑d∣ndkσ0(n) 通常简记做 d(n) 或 τ(n) , σ1(n) 通常简记做 σ(n)
- 欧拉函数: φ(n)=∑ni=1[gcd(i,n)=1]
- 莫比乌斯函数: μ(n)={1n=10∃d:d2∣n(−1)ω(n)otherwise 其中 ω(n) 表示 n 的本质不同质因子个数,是一个加性函数
Dirichlet卷积
定义
定义两个数论函数 f,g 的Dirichlet卷积为
(f∗g)(n)=∑d∣nf(d)g(nd)性质
Dirichlet卷积满足交换律和结合律
其中 ε 为Dirichlet卷积的单位元(任何函数卷 ϵ 都为其本身)
例子
ε=μ∗1⇔ε(n)=∑d∣nμ(d)d=1∗1⇔d(n)=∑d∣n1σ=d∗1⇔ε(n)=∑d∣ndφ=μ∗ID⇔φ(n)=∑d∣nd⋅μ(nd)莫比乌斯函数
定义
μ 为莫比乌斯函数
性质
莫比乌斯函数不但是积性函数,还有如下性质:
μ(n)={1n=10n 含有平方因子(−1)kk 为 n 的本质不同质因子个数证明
ε(n)={1n=10n≠1其中 ε(n)=∑d∣nμ(d) 即 ε=μ∗1
设 n=k∏i=1pici,n′=k∏i=1pi
那么 ∑d∣nμ(d)=∑d∣n′μ(d)=k∑i=0Cik⋅(−1)k
根据二项式定理,易知该式子的值在 k=0 即 n=1 时的值为 1 否则为 0 ,这也同时证明了 ∑d∣nμ(d)=[n=1]
补充结论
反演推论: [gcd(i,j)=1]⇔∑d∣gcd(i,j)μ(d)
- **直接推导:**如果看懂了上一个结论,这个结论稍加思考便可以推出:如果 gcd(i,j)=1 的话,那么代表着我们按上个结论中枚举的那个 n 是 1 ,也就是式子的值是 1 ,反之,有一个与 [gcd(i,j)=1] 相同的值:0
- **利用 ε 函数:**根据上一结论, [gcd(i,j)=1]⇒ε(gcd(i,j)) ,将 ε 展开即可。
线性筛
由于 μ 函数为积性函数,因此可以线性筛莫比乌斯函数(线性筛基本可以求所有的积性函数,尽管方法不尽相同)。
Code
c++ ▽void getMu() {
mu[1] = 1;
for (int i = 2; i <= n; ++i) {
if (!flg[i]) p[++tot] = i, mu[i] = -1;
for (int j = 1; j <= tot && i * p[j] <= n; ++j) {
flg[i * p[j]] = 1;
if (i % p[j] == 0) {
mu[i * p[j]] = 0;
break;
}
mu[i * p[j]] = -mu[i];
}
}
}
拓展
φ∗1=ID(ID 函数即 f(x)=x)将 n 分解质因数: n=k∏i=1pici
首先,因为 φ 是积性函数,故只要证明当 n′=pc 时 φ∗1=∑d∣n′φ(n′d)=ID 成立即可。
因为 p 是质数,于是 d=p0,p1,p2,⋯,pc
易知如下过程
φ∗1=∑d∣nφ(nd)=c∑i=0φ(pi)=1+p0⋅(p−1)+p1⋅(p−1)+⋯+pc−1⋅(p−1)=pc=ID该式子两侧同时卷 μ 可得 φ(n)=∑d∣nd⋅μ(nd)
莫比乌斯反演
公式
设 f(n),g(n) 为两个数论函数
如果有 f(n)=∑d∣ng(d)
那么有 g(n)=∑d∣nμ(d)f(nd)
证明
**暴力计算:** ∑d∣nμ(d)f(nd)=∑d∣nμ(d)∑k∣ndg(k)=∑k∣ng(k)∑d∣nkμ(d)=g(n)
用 ∑d∣ng(d) 来替换 f(nd) ,再变换求和顺序。最后一步转为的依据: ∑d∣nμ(d)=[n=1]
因此在 nk=1 时第二个和式的值才为 1 。此时 n=k ,故原式等价于 ∑k∣n[n=k]⋅g(k)=g(n)
运用卷积:
原问题为:已知 f=g∗1 ,证明 g=f∗μ
易知如下转化: f∗μ=g∗1∗μ⇒f∗μ=g (其中 1∗μ=ε )
莫比乌斯反演拓展
对于数论函数 f,g 和完全积性函数 t 且 t(1)=1 :
f(n)=∑ni=1t(i)g(⌊ni⌋)⇔g(n)=∑ni=1μ(i)t(i)f(⌊ni⌋)我们来证明一下:
g(n)=n∑i=1μ(i)t(i)f(⌊ni⌋)=n∑i=1μ(i)t(i)⌊ni⌋∑j=1t(j)g(⌊⌊ni⌋j⌋)=n∑i=1μ(i)t(i)⌊ni⌋∑j=1t(j)g(⌊nij⌋)=n∑T=1n∑i=1μ(i)t(i)⌊ni⌋∑j=1[ij=T]t(j)g(⌊nT⌋)【先枚举 ij 乘积】=n∑T=1∑i|Tμ(i)t(i)t(Ti)g(⌊nT⌋)【⌊ni⌋∑j=1[ij=T]对答案的贡献为 1,于是省略】=n∑T=1g(⌊nT⌋)∑i|Tμ(i)t(i)t(Ti)=n∑T=1g(⌊nT⌋)∑i|Tμ(i)t(T)【t 是完全积性函数】=n∑T=1g(⌊nT⌋)t(T)∑i|Tμ(i)=n∑T=1g(⌊nT⌋)t(T)ε(T)【μ∗1=ε】=g(n)t(1)【当且仅当 T=1,ε(T)=1时】=g(n)◻解法二:
转化一下,可以将式子写成
n∑d=1⌊nd⌋∑i=1⌊md⌋∑j=1ijd⋅[gcd(i,j)=1]=n∑d=1d⌊nd⌋∑i=1⌊md⌋∑j=1ij∑t∣gcd(i,j)μ(t)=n∑d=1d⌊nd⌋∑i=1⌊md⌋∑j=1ij⌊nd⌋∑t=1μ(t)[t∣gcd(i,j)]=n∑d=1d⌊nd⌋∑t=1t2μ(t)⌊ntd⌋∑i=1⌊mtd⌋∑j=1ij[1∣gcd(i,j)]=n∑d=1d⌊nd⌋∑t=1t2μ(t)⌊ntd⌋∑i=1⌊mtd⌋∑j=1ij容易知道
∑ni=1∑mj=1ij=n(n+1)2⋅m(m+1)2设 sum(n,m)=∑ni=1∑mj=1ij ,继续接着前面的往下推
n∑d=1d⌊nd⌋∑t=1t2μ(t)⌊ntd⌋∑i=1⌊mtd⌋∑j=1ij=n∑d=1d⌊nd⌋∑t=1t2μ(t)⋅sum(⌊ntd⌋,⌊mtd⌋)=n∑T=1sum(⌊nT⌋,⌊mT⌋)∑d∣Td⋅(Td)2μ(Td)=n∑T=1sum(⌊nT⌋,⌊mT⌋)(T∑d∣Td⋅μ(d))这时我们只要对每个 T 预处理出 T∑d∣Td⋅μ(d) 的值就行了,考虑如何快速求解
设 f(n)=∑d∣nd⋅μ(d)
实际上 f 可以用线性筛筛出,具体的是
f(n)={1−n,n∈primesf(xp),p2∣nf(xp)⋅f(p),p2∤其中 表示 的最小质因子
总时间复杂度