「莫比乌斯反演」学习笔记

个人赶脚这个东西非常好玩。
决定安利给朋友所以有了这篇笔记。

数论函数

在数论上,数论函数指定义域为正整数、值域为实/复数的函数。
通俗地讲,我们 OI 接触到的大部分函数都是数论函数,比如:

  • 元函数 ϵ(n)=[n=1]\epsilon(n) = [n = 1]
  • 欧拉函数 φ(n)=i=1n1[gcd(n,i)=1]\varphi(n) = \sum\limits_{i = 1}^{n - 1} [\gcd(n,i) = 1]
  • 约数个数函数 d(n)=in1d(n) = \sum\limits_{i | n} 1
  • 约数和函数 σ(n)=ini\sigma(n) = \sum\limits_{i | n} i

积性函数

对于一个数论函数 ff,若对于所有 gcd(i,j)=1\gcd(i,j) = 1i,ji,j,都有 f(ij)=f(i)f(j)f(ij) = f(i) f(j),则称函数 ff积性函数

特别地,如果对于所有没有限制的 i,ji,j 上式仍成立,则称该函数是完全积性函数

狄利克雷卷积

记两个数论函数 f,gf,g狄利克雷卷积fgf * g
(fg)(n)=dnf(d)g(nd)(f * g)(n) = \sum\limits_{d | n} f(d) g(\dfrac n d)

显然狄利克雷卷积具有交换律与结合律。

莫比乌斯函数

把正整数 nn 分解为质因数相乘的形式 n=i=1mpicin = \sum\limits_{i = 1}^m {p_i}^{c_i},有

μ(n)={1,n=10,i[1,m],ci>1(1)m,i[1,m],ci=1\mu(n) = \begin{cases} 1, & n = 1 \\ 0, & \exists i \in [1,m],c_i > 1 \\ (-1)^m, & \forall i \in [1,m],c_i = 1 \end{cases}

显然莫比乌斯函数也是积性函数。

如果要求 μ(n)\mu(n),分解质因数即可。

如果要求 μ(1)μ(n)\mu(1) \sim \mu(n),可以线性筛。
伪代码:

1
2
3
4
5
6
7
8
9
10
11
getMu(n)
mu[1] = 1
for i in [2,n]
if vis[i] == 0
prime[++cnt] = i
mu[i] = -1
for j in [1,cnt] and i * prime[j] <= n
vis[i * prime[j]] = 1
if i mod prime[j] == 0
break
mu[i * prime[j]] = -mu[i]

有一个比较显然的性质:dnμ(d)=[n=1]\sum\limits_{d | n} \mu(d) = [n = 1]

证明:
首先,显然 也是积性函数。

然后考虑一个质数 pp

考虑合数 x,x>1x,x > 1,将它分解为质因子相乘的形式 x=i=1mpicix = \prod\limits_{i = 1}^m {p_i}^{c_i}

证毕。

然后有莫比乌斯反演公式:
如果有数论函数 ffFF,满足 F(n)=dnf(d)F(n) = \sum\limits_{d | n} f(d),有 f(n)=dnF(d)μ(nd)f(n) = \sum\limits_{d | n} F(d) \mu(\dfrac n d)

证明:
我们让 F(n)=dnf(d)F(n) = \sum\limits_{d | n} f(d) 这个式子等号两边都卷上 μ\mu,即
由于狄利克雷卷积有交换与结合律,所以
所以 f=Fμf = F * \mu

这个玩意有一个更为常用的形式:若 F(n)=ndf(d)F(n) = \sum\limits_{n | d} f(d),那么 f(n)=ndF(d)μ(dn)f(n) = \sum\limits_{n | d} F(d) \mu(\dfrac d n)

其实莫比乌斯函数是基于容斥原理的。

例题 - Zap

给定 n,m,kn,m,k,求 i=1nj=1m[gcd(i,j)=k]\sum\limits_{i = 1}^n \sum\limits_{j = 1}^m [\gcd(i,j) = k]
多组询问。

f(x)=i=1nj=1m[gcd(i,j)=x],F(x)=xdf(d)=nxmxf(x) = \sum\limits_{i = 1}^n \sum\limits_{j = 1}^m [\gcd(i,j) = x],F(x) = \sum\limits_{x | d} f(d) = \lfloor \dfrac n x \rfloor \lfloor \dfrac m x \rfloor
于是 f(x)=xdμ(dx)ndmdf(x) = \sum\limits_{x | d} \mu(\dfrac d x) \lfloor \dfrac n d \rfloor \lfloor \dfrac m d \rfloor
考虑把枚举的东西换成 dx\dfrac d x,有 f(x)=ximin(n,m)μ(i)nximxif(x) = \sum\limits_{xi \le \min(n,m)} \mu(i) \lfloor \dfrac n {xi} \rfloor \lfloor \dfrac m {xi} \rfloor

但是这样还没完,我们仍然没法直接做。
换个角度思考,i=1nj=1m[gcd(i,j)=k]\sum\limits_{i = 1}^n \sum\limits_{j = 1}^m [\gcd(i,j) = k] 相当于 kinkjm[gcd(i,j)=1]\sum\limits_{ki \le n} \sum\limits_{kj \le m} [\gcd(i,j) = 1]
于是原式变为 i=1min(n,m)μ(i)nkimki\sum\limits_{i = 1}^{\min(n,m)} \mu(i) \lfloor \dfrac {\lfloor \frac n k \rfloor} i \rfloor \lfloor \dfrac {\lfloor \frac m k \rfloor} i \rfloor

运用数论分块即可解决。

arknights