Processing math: 96%
2019-08-06  2024-09-15    1776 字  4 分钟

莫比乌斯反演是数论中的重要内容,对于一些函数 f(n) ,如果很难直接求出它的值,而容易求出其倍数和或约数和 g(n) ,那么可以通过莫比乌斯反演简化运算,求得 f(n) 的值。

开始学习莫比乌斯反演前我们需要一些前置知识:积性函数、Dirichlet卷积、莫比乌斯函数

数论分块与整除相

引理 1

a,b,cZ,abc=abc

略证

ab=ab+r(0r<1)abc=ab1c=1c(ab+r)=abc+rc=abc

引理 2

nN,{nddN}2n

V 表示集合 V 的元素个数

略证

对于 dnndn 种取值

对于 d>n ,有 ndn ,也只有 n 种取值

综上得证

数论分块

数论分块的过程大概如下:考虑含有 ni 的求和式子( n 为常数)

对于任意一个 i(in) ,我们需要找到一个最大的 j(ijn) ,使得 ni=nj

j=nni

略证

nininninni=i=iinni

j=nni

利用上述结论,我们每次以 [i,j] 为一块,分块求和即可

积性函数

定义

gcd(x,y)=1f(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)=dxf(d)g(xd)

例子

  • 单位函数: ϵ(n)=[n=1]
  • 恒等函数: idk(n)=nkid1(n) 通常记做 id(n)
  • 常数函数: 1(n)=1
  • 除数函数: σk(n)=dndkσ0(n) 通常简记做 d(n)τ(n)σ1(n) 通常简记做 σ(n)
  • 欧拉函数: φ(n)=ni=1[gcd(i,n)=1]
  • 莫比乌斯函数: μ(n)={1n=10d:d2n(1)ω(n)otherwise 其中 ω(n) 表示 n 的本质不同质因子个数,是一个加性函数

Dirichlet卷积

定义

定义两个数论函数 f,g 的Dirichlet卷积为

(fg)(n)=dnf(d)g(nd)

性质

Dirichlet卷积满足交换律和结合律

其中 ε 为Dirichlet卷积的单位元(任何函数卷 ϵ 都为其本身)

例子

ε=μ1ε(n)=dnμ(d)d=11d(n)=dn1σ=d1ε(n)=dndφ=μIDφ(n)=dndμ(nd)

莫比乌斯函数

定义

μ 为莫比乌斯函数

性质

莫比乌斯函数不但是积性函数,还有如下性质:

μ(n)={1n=10n 含有平方因子(1)kk 为 n 的本质不同质因子个数

证明

ε(n)={1n=10n1

其中 ε(n)=dnμ(d)ε=μ1

n=ki=1pici,n=ki=1pi

那么 dnμ(d)=dnμ(d)=ki=0Cik(1)k

根据二项式定理,易知该式子的值在 k=0n=1 时的值为 1 否则为 0 ,这也同时证明了 dnμ(d)=[n=1]

补充结论

反演推论: [gcd(i,j)=1]dgcd(i,j)μ(d)

  • **直接推导:**如果看懂了上一个结论,这个结论稍加思考便可以推出:如果 gcd(i,j)=1 的话,那么代表着我们按上个结论中枚举的那个 n1 ,也就是式子的值是 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=ki=1pici

首先,因为 φ 是积性函数,故只要证明当 n=pcφ1=dnφ(nd)=ID 成立即可。

因为 p 是质数,于是 d=p0,p1,p2,,pc

易知如下过程

φ1=dnφ(nd)=ci=0φ(pi)=1+p0(p1)+p1(p1)++pc1(p1)=pc=ID

该式子两侧同时卷 μ 可得 φ(n)=dndμ(nd)

莫比乌斯反演

公式

f(n),g(n) 为两个数论函数

如果有 f(n)=dng(d)

那么有 g(n)=dnμ(d)f(nd)

证明

**暴力计算:** dnμ(d)f(nd)=dnμ(d)kndg(k)=kng(k)dnkμ(d)=g(n)

dng(d) 来替换 f(nd) ,再变换求和顺序。最后一步转为的依据: dnμ(d)=[n=1]

因此在 nk=1 时第二个和式的值才为 1 。此时 n=k ,故原式等价于 kn[n=k]g(k)=g(n)

运用卷积:

原问题为:已知 f=g1 ,证明 g=fμ

易知如下转化: fμ=g1μfμ=g (其中 1μ=ε

莫比乌斯反演拓展

对于数论函数 f,g 和完全积性函数 tt(1)=1

f(n)=ni=1t(i)g(ni)g(n)=ni=1μ(i)t(i)f(ni)

我们来证明一下:

g(n)=ni=1μ(i)t(i)f(ni)=ni=1μ(i)t(i)nij=1t(j)g(nij)=ni=1μ(i)t(i)nij=1t(j)g(nij)=nT=1ni=1μ(i)t(i)nij=1[ij=T]t(j)g(nT)【先枚举 ij 乘积】=nT=1i|Tμ(i)t(i)t(Ti)g(nT)nij=1[ij=T]对答案的贡献为 1,于是省略】=nT=1g(nT)i|Tμ(i)t(i)t(Ti)=nT=1g(nT)i|Tμ(i)t(T)【t 是完全积性函数】=nT=1g(nT)t(T)i|Tμ(i)=nT=1g(nT)t(T)ε(T)μ1=ε=g(n)t(1)【当且仅当 T=1,ε(T)=1时】=g(n)

解法二:

转化一下,可以将式子写成

nd=1ndi=1mdj=1ijd[gcd(i,j)=1]=nd=1dndi=1mdj=1ijtgcd(i,j)μ(t)=nd=1dndi=1mdj=1ijndt=1μ(t)[tgcd(i,j)]=nd=1dndt=1t2μ(t)ntdi=1mtdj=1ij[1gcd(i,j)]=nd=1dndt=1t2μ(t)ntdi=1mtdj=1ij

容易知道

ni=1mj=1ij=n(n+1)2m(m+1)2

sum(n,m)=ni=1mj=1ij ,继续接着前面的往下推

nd=1dndt=1t2μ(t)ntdi=1mtdj=1ij=nd=1dndt=1t2μ(t)sum(ntd,mtd)=nT=1sum(nT,mT)dTd(Td)2μ(Td)=nT=1sum(nT,mT)(TdTdμ(d))

这时我们只要对每个 T 预处理出 TdTdμ(d) 的值就行了,考虑如何快速求解

f(n)=dndμ(d)

实际上 f 可以用线性筛筛出,具体的是

f(n)={1n,nprimesf(xp),p2nf(xp)f(p),p2

其中 pp 表示 nn 的最小质因子

总时间复杂度 O(n+n)O(n+\sqrt{n})

例题

「HAOI 2011」Problem b

「SPOJ 5971」LCMSUM

「BZOJ 2154」Crash 的数字表格

「SDOI2015」约数个数和

「luogu 3768」简单的数学题