写在前面

这篇博客用来记录一下我学习莫比乌斯反演的过程,以及我是如何理解它的。

期间参考了大量其他博客,这里列出表示感谢:

  1. 莫比乌斯反演 by OI-wiki
  2. 莫比乌斯反演-让我们从基础开始 by An_Account
  3. 莫比乌斯反演-从莫比乌斯到欧拉 by An_Account
  4. 莫比乌斯反演学习笔记 by LNRBHAW
  5. 莫比乌斯函数 by Grary
  6. 数论函数 - 莫比乌斯函数与莫比乌斯反演 - 基础杜教筛 by zhouzhendong

参考的博客包括但不限于以上这些,有些看过的博客忘记了(逃

另外,如果本篇博客涉及侵权,请您及时联系我修改,以免造成不必要的损失。

前置知识

学习莫比乌斯反演以前,需要先了解的一些前置知识。

积性函数

积性函数是数论中一个非常重要的概念,常常可以利用其性质来进行数论分块优化。

  • 定义

gcd(x,y)=1gcd(x, y) = 1f(xy)=f(x)f(y)f(xy) = f(x)f(y),则称函数f(x)f(x)为积性函数。

扩展:若对于任意(x,y)(x, y)满足f(xy)=f(x)f(y)f(xy) = f(x)f(y),则称函数f(x)f(x)为完全积性函数。

  • 性质

f(x)f(x)g(x)g(x)均为积性函数,则下列函数h(x)h(x)也为积性函数:

  1. h(x)=f(xp)h(x) = f(x^p)
  2. h(x)=fp(x)h(x) = f^p(x)
  3. h(x)=f(x)g(x)h(x) = f(x)g(x)
  4. h(x)=dxf(d)g(xd)h(x) = \displaystyle\sum_{d|x} {f(d)g(\frac{x}{d})}

所有的积性函数都可以用线性筛求。

其实4就是之后会提到的狄利克雷卷积。

  • 常见的积性函数

    • 单位函数:ε(n)=[n=1]\varepsilon(n) = [n=1],也常写作ε\varepsilon
    • 恒等函数:idk(n)=nkid_k(n) = n^kid1(n)id_1(n)常写作id(n)id(n)
    • 常数函数1(n)=1\bold{1}(n) = 1,常常直接用1\bold{1}代替
    • 除数函数:σk(n)=dndk\sigma_k(n) = \displaystyle\sum_{d|n}{d^k}σ0(n)\sigma_0(n)通常记为d(n)d(n),即常数函数,σ1(n)\sigma_1(n)通常记为σ(n)\sigma(n)
    • 欧拉函数:φ(n)=i=1n[gcd(i,n)=1]\varphi(n) = \displaystyle\sum_{i=1}^{n} {[\gcd(i, n) = 1]}
    • 莫比乌斯函数: μ(d)={1,d=0(1)k,d=p1p2pk,pipj0,others\mu(d) = \begin{cases} 1, & {d = 0} \\ {(-1)} ^k, & {d = p_1 \cdot p_2 \dots p_k}, \forall p_i \not = p_j \\ 0, & {others} \end{cases}

本篇文章出现的所有[x][x]表示若xx为真值则[x][x]为1,否则为00,且接下来的内容遇到以上函数,可以简写的将尽可能地用简写代替。

狄利克雷卷积

也叫狄利克雷乘积(Dirichlet product),是数论重要知识之一,也是推导、证明莫比乌斯反演的关键。

  • 定义

定义两个数论函数f(n),g(n)f(n), g(n)的狄利克雷卷积为:

(f(n)g(n))(n)=dnf(d)g(nd)(f(n) * g(n))(n) = \displaystyle\sum_{d|n}{f(d)g(\frac{n}{d})}

(f(n)g(n))(n)(f(n) * g(n))(n)常写作fgf * g

注:数论函数指定义在N+N_+上的函数,满足积性和加性性质。

另外,为了更方便地区分,本文所有fgf*g代表狄利克里卷积,而普通乘法则会写成fgf \cdot gfgfg

  • 性质

  1. 狄利克雷卷积满足交换律、结合律和分配律(前提是函数均满足加性)。

fg=gff * g = g * f

(fg)h=f(gh)(f * g) * h = f * (g * h)

f(g+h)=fg+fhf * (g + h) = f * g + f * h

  1. ε\varepsilon为狄利克雷卷积的幺元(单位元)。

f(x),xN+    fε=εf=f\forall f(x), x \in N_+ \implies f * \varepsilon = \varepsilon * f = f

  1. f(x)f(x)g(x)g(x)均为积性函数,则fgf*g也是积性函数,反之若fgf*gg(x)g(x)均为积性函数,则f(x)f(x)也是积性函数。

  2. g(x)g(x)是完全积性函数,且h(x)=fgh(x) = f*g,则f(x)=h(μg)f(x) = h* (\mu \cdot g)

  • 一些例子

    • μ1=dnμ(d)=dnμ(nd)=1μ=ε\mu * \bold{1} = \displaystyle\sum_{d|n}{\mu(d)} = \displaystyle\sum_{d|n}{\mu(\frac{n}{d})} = \bold{1} * \mu = \varepsilon
    • 11=dn1=d(n)\bold{1} * \bold{1} = \displaystyle\sum_{d|n}{1} = d(n)
    • μid=dndμ(nd)=φ(n)\mu * id = \displaystyle\sum_{d|n}{d \cdot \mu(\frac{n}{d})} = \varphi(n)
    • φ1=dnφ(nd)=id(n)\varphi * 1 = \displaystyle\sum_{d|n}{\varphi(\frac{n}{d})} = id(n)

莫比乌斯函数

  • 定义

μ(d)={1,d=0(1)k,d=p1p2pk,pipj0,others\mu(d) = \begin{cases} 1, & {d = 0} \\ {(-1)} ^k, & {d = p_1 \cdot p_2 \dots p_k}, \forall p_i \not = p_j \\ 0, & {others} \end{cases}

  • 性质

    1. μ\mu是积性函数。
    2. dnμ(d)=ε\displaystyle\sum_{d|n}{\mu(d)} = \varepsilon
    3. dgcd(i,j)μ(d)=ε(gcd(i,j))=[gcd(i,j)=1]\displaystyle\sum_{d|\gcd(i, j)}{\mu(d)} = \varepsilon(\gcd(i, j)) = [\gcd(i, j) = 1]
    4. dnμ(d)d=φ(n)n\displaystyle\sum_{d|n} {\frac{\mu(d)}{d}} = {\frac{\varphi(n)}{n}}
  • 线性筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int MAX_N = 1e6 + 10;
bool vis[MAX_N];
int CNT, prime[MAX_N], mu[MAX_N];

void make_mobius() {
memset(vis, false, sizeof(vis));
mu[1] = 1;
CNT = 0;
for(int i = 2; i < MAX_N; ++i) {
if(!vis[i]) {
prime[++CNT] = i;
mu[i] = -1;
}
for(int j = 1; j <= CNT && i*prime[j] < MAX_N; ++j) {
vis[i*prime[j]] = true;
if(i % prime[j] == 0) {
mu[i * prime[j]] = 0;
break ;
} else mu[i * prime[j]] = -mu[i];
}
}
}

莫比乌斯反演

  • 定义

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

f(n)=dng(d)f(n) = \displaystyle\sum_{d|n} {g(d)}

那么有

g(n)=dnμ(d)f(nd)g(n) = \displaystyle\sum_{d|n} {\mu(d)f(\frac{n}{d})}

根据狄利克雷卷积的性质,当然也可以

f(n)=ndg(d)g(n)=ndμ(dn)f(d)f(n) = \displaystyle\sum_{n|d} {g(d)} \rArr g(n) = \displaystyle\sum_{n|d} {\mu(\frac{d}{n})f(d)}

  • 证明

其实第一个反演公式还蛮好证明的:

f(n)=dng(d)\because f(n) = \displaystyle\sum_{d|n} {g(d)}

dnμ(d)f(nd)=dnμ(d)kndg(k)\therefore\displaystyle\sum_{d|n} {\mu(d)f(\frac{n}{d})} = \displaystyle\sum_{d|n} {\mu(d)} \displaystyle\sum_{k|\frac{n}{d}}{g(k)}

根据积性函数性质得

dnμ(d)kndg(k)=dng(d)kndμ(k)\displaystyle\sum_{d|n} {\mu(d)} \displaystyle\sum_{k|\frac{n}{d}}{g(k)} = \displaystyle\sum_{d|n}{g(d)} \displaystyle\sum_{k|\frac{n}{d}} {\mu(k)}

dnμ(d)=[n=1]kndμ(k)=[nd=1]\because \displaystyle\sum_{d|n}{\mu(d)} = [n = 1] \rArr \displaystyle\sum_{k|\frac{n}{d}} {\mu(k)} = \bigg[\frac{n}{d} = 1\bigg]

dng(d)kndμ(k)=dng(d)[n=d]=g(n)\therefore \displaystyle\sum_{d|n}{g(d)} \displaystyle\sum_{k|\frac{n}{d}} {\mu(k)} = \displaystyle\sum_{d|n}{g(d) \cdot [n=d]} = g(n)

同理可以证第二个反演公式,证毕。

不过利用狄利克雷卷积证明更快:

第一个反演公式可以转换为

f=g1g=μff = g * \bold{1} \rArr g = \mu * f

则有

μf=μg1=g(μ1)=gε=g\mu * f = \mu * g * \bold{1} = g * (\mu * \bold{1}) = g * \varepsilon = g

证毕。

一些应用

了解了莫比乌斯函数及其反演以后,我们就可以来学习和推导一些东西。

  • 简单例子:推导欧拉函数

假设让你求这样一个式子:

i=1n[gcd(i,n)=1],(1n107)\sum_{i=1}^{n}{[\gcd(i, n)=1]},(1 \leq n \leq 10^7)

根据上面提到的莫比乌斯函数的性质3,可以将原式转化为

i=1ndgcd(i,n)μ(d)\sum_{i=1}^{n}{\sum_{d|gcd(i, n)}\mu(d)}

当然这样还是不好求,我们需要转换思路,转而去枚举dd,易知d[1,n]d \in [1, n],则可将上式化为

d=1nμ(d)i=1n[di]=d=1nμ(d)nd\begin{gathered} &\sum_{d=1}^{n}{\mu(d) \sum_{i=1}^{n}{[d|i]}} \\ = &\sum_{d=1}^{n}{\mu(d) \left\lfloor{\frac{n}{d}}\right\rfloor} \end{gathered}

实际上这就是我们喜闻乐见的欧拉函数φ(n)\varphi(n)

  • 简单例子扩展

假设现在让你求:

i=1nj=1m[gcd(i,j)=k],(1knm105)\sum_{i=1}^{n}\sum_{j=1}^{m}{[\gcd(i, j)=k]},(1 \leq k \leq n \leq m \leq 10^5)

注意:从这里开始若下文的nnmm没有特殊说明,都是这个量级。

看起来比简单例子难很多?实际上没有,我们依然可以用简单例子的思路。

当然,第一件事是将[gcd(i,j)=k][\gcd(i, j) = k]转换成[gcd(i,j)=1][\gcd(i, j) = 1]

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

这一步应该很好理解吧?相当于i,ji, j都除掉最大公因数kk(逃

接下来的一顿操作就和之前一样了

i=1nkj=1mk[gcd(i,j)=1]=i=1nkj=1mkdgcd(i,j)μ(d)=d=1nkμ(d)i=1nk[di]j=1mk[dj]=d=1nkμ(d)nkdmkd\begin{gathered} &\sum_{i=1}^{\left\lfloor{\frac{n}{k}}\right\rfloor}\sum_{j=1}^{\left\lfloor{\frac{m}{k}}\right\rfloor}{[\gcd(i, j)=1]} \\ = &\sum_{i=1}^{\left\lfloor{\frac{n}{k}}\right\rfloor}\sum_{j=1}^{\left\lfloor{\frac{m}{k}}\right\rfloor}{\sum_{d|gcd(i, j)}\mu(d)} \\ = &\sum_{d=1}^{\left\lfloor{\frac{n}{k}}\right\rfloor}{\mu(d)}\sum_{i=1}^{\left\lfloor{\frac{n}{k}}\right\rfloor}{[d|i]}\sum_{j=1}^{\left\lfloor{\frac{m}{k}}\right\rfloor}{[d|j]} \\ = &\sum_{d=1}^{\left\lfloor{\frac{n}{k}}\right\rfloor}{\mu(d)\left\lfloor{\frac{n}{kd}}\right\rfloor\left\lfloor{\frac{m}{kd}}\right\rfloor} \end{gathered}

如果你看到这里能够理解,说明你对莫比乌斯函数已经有一定感觉了。

  • 另一个简单例子:求最大公约数的和

再来求这样一个式子:

i=1ngcd(i,n)\sum_{i=1}^{n}{\gcd(i, n)}

有了前面莫比乌斯的套路,那我们我们就有了第一步——化gcd\gcd为虚无!

这里当然不能直接地将gcd\gcd转化为μ\mu,我们需要借助φ\varphi的性质:

dnφ(d)=ndgcd(i,n)φ(d)=gcd(i,n)\sum_{d|n}{\varphi(d)} = n \rArr \sum_{d|gcd(i, n)}{\varphi(d)} = \gcd(i, n)

然后就成功将原式子转化成

i=1ndgcd(i,n)φ(d)\sum_{i=1}^{n}\sum_{d|gcd(i, n)}{\varphi(d)}

显而易见地可以用上前面的套路直接再转化成

d=1nφ(d)i=1n[di]d=1nφ(d)nd\sum_{d=1}^{n}{\varphi(d) \sum_{i=1}^{n}{[d|i]}} \rArr \sum_{d=1}^{n}{\varphi(d) \left\lfloor{\frac{n}{d}}\right\rfloor}

喜闻乐见地,我们得到了一个和第一个简单例子类似的式子。

自然地,对于这个式子也有一定的扩展,推导方式和之前类似,这里直接给结果。

i=1nj=1mgcd(i,j)=d=1nφ(d)ndmd\sum_{i=1}^{n}{\sum_{j=1}^{m}\gcd(i, j)} = \sum_{d=1}^{n}{\varphi(d)\left\lfloor{\frac{n}{d}}\right\rfloor\left\lfloor{\frac{m}{d}}\right\rfloor}

  • 扩展:求最小公倍数的和

i=1nlcm(i,n)i=1ningcd(i,n)\sum_{i=1}^{n}lcm(i, n) \rArr \sum_{i=1}^{n}{\frac{i \cdot n}{\gcd(i, n)}}

易知gcd(a,b)=gcd(ba,b)\gcd(a, b) = \gcd(b-a, b),则上式可化为

12(i=1n1ingcd(i,n)+i=1n1(ni)ngcd(ni,n))+n=12i=1n1n2gcd(i,n)+n\begin{gathered} &\frac{1}{2} \cdot \left({\sum_{i=1}^{n-1}{\frac{i \cdot n}{\gcd(i, n)}} + \sum_{i=1}^{n-1}{\frac{(n-i) \cdot n}{\gcd(n-i, n)}}}\right) + n \\ = &\frac{1}{2} \cdot \sum_{i=1}^{n-1}{\frac{n^2}{\gcd(i, n)}} + n \end{gathered}

有了之前的经验,我们就要想办法把gcd(i,n)\gcd(i, n)相同的项合并,于是我们枚举d=gcd(i,n)d = gcd(i, n),易知共有φ(nd)\varphi(\frac{n}{d})个。则上式可化为

12d<n,dnn2φ(nd)d+n\frac{1}{2} \cdot \sum_{d<n,d|n}^{}{\frac{n^2 \cdot \varphi(\frac{n}{d})}{d}} + n

再令d=ndd' = \frac{n}{d}

n2d>1,dndφ(d)+n\frac{n}{2} \cdot \sum_{d'>1,d'|n}^{}{d' \varphi(d')} + n

g(n)=d>1,dndφ(d)g(n) = \displaystyle\sum_{d'>1,d'|n}^{}{d' \varphi(d')},易知g(n)g(n)是积性函数,可以利用其性质进行线性筛。

这里用了一种巧妙地方式化简,如果用常规的莫比乌斯反演套路推导:

i=1nlcm(i,n)=i=1ningcd(i,n)=ndn1di=1n[gcd(i,n)=d]i=ndn1di=1nd[gcd(i,nd)=1]id=ndni=1nd[gcd(i,nd)=1]i\begin{gathered} &\sum_{i=1}^{n}lcm(i, n) = \sum_{i=1}^{n}{\frac{i \cdot n}{\gcd(i, n)}} \\ = &n \cdot \sum_{d|n}^{} {\frac{1}{d}} \cdot {\sum_{i=1}^{n} [\gcd(i, n) = d] \cdot i} \\ = &n \cdot \sum_{d|n}^{} {\frac{1}{d}} \cdot {\sum_{i=1}^{\frac{n}{d}} [\gcd(i, \frac{n}{d}) = 1] \cdot i \cdot d} \\ = &n \cdot \sum_{d|n}^{} {\sum_{i=1}^{\frac{n}{d}} [\gcd(i, \frac{n}{d}) = 1] \cdot i} \end{gathered}

根据欧拉函数的性质有gcd(i,n)=1ni=nφ(n)2(n>1)\displaystyle\sum_{\gcd(i, n) = 1}^{n}{i} = \frac{n \cdot \varphi(n)}{2}(n>1),上式可化为

ndnndφ(nd)2n \cdot \sum_{d|n}^{} \frac{\frac{n}{d} \cdot \varphi(\frac{n}{d})}{2}

同样令d=ndd' = \frac{n}{d}

ndndφ(d)2n \cdot \sum_{d'|n}^{} \frac{d' \varphi(d')}{2}

推导到这里其实可以发现一个问题:我们会在计算过程中不小心忽略了d=nd=nd=1d'=1的情况,所以我们最后需要再加上lcm(n,n)=nlcm(n, n) = n,即最终答案为:

nd>1,dndφ(d)2+nn \cdot \sum_{d'>1, d'|n}^{} \frac{d' \varphi(d')}{2} + n

和我们上面巧妙推导方式的结果是一样的。

有些文章会写成

n2(dndφ(d)+1)\frac{n}{2} \cdot \left(\sum_{d'|n}^{}{d' \varphi(d')} + 1\right)

本质上是一样的,原因就在于n=1n=1时,gcd(i,n)=1ni=1\displaystyle\sum_{gcd(i, n) = 1}^{n}{i} = 1

  • 再扩展:二维最小公倍数求和

i=1nj=1mlcm(i,j)i=1nj=1mijgcd(i,j)\sum_{i=1}^{n}{\sum_{j=1}^{m}lcm(i, j)} \rArr \sum_{i=1}^{n}{\sum_{j=1}^{m}{\frac{i \cdot j}{\gcd(i, j)}}}

这里显然不能再用上面非传统的化简思路,还得用回常规套路:

=i=1nj=1md=1nijd[gcd(i,j)=d]=d=1ni=1ndj=1mdijd2d[gcd(i,j)=1]=d=1ndi=1ndj=1mdij[gcd(i,j)=1]=d=1ndi=1ndj=1mdijkgcd(i,j)μ(k)=d=1ndk=1ndμ(k)k2i=1ndkj=1mdkij\begin{gathered} = &\sum_{i=1}^{n}{\sum_{j=1}^{m}{\sum_{d=1}^{n}{\frac{i \cdot j}{d} \cdot [\gcd(i, j) = d]}}} \\ = &\sum_{d=1}^{n}{\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}{\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}{\frac{i \cdot j \cdot d^2}{d} \cdot [\gcd(i, j) = 1]}}} \\ = &\sum_{d=1}^{n}{d \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}{\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}{i \cdot j \cdot [\gcd(i, j) = 1]}}} \\ = &\sum_{d=1}^{n}{d \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}{\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}{i \cdot j \cdot \sum_{k|\gcd(i,j)}^{}{\mu(k)}}}} \\ = &\sum_{d=1}^{n}{d \cdot \sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}{\mu(k)} \cdot k^2 \cdot \sum_{i=1}^{\lfloor\frac{n}{dk}\rfloor}{\sum_{j=1}^{\lfloor\frac{m}{dk}\rfloor}{i \cdot j}}} \\ \end{gathered}

到这一步,已经是一个朴素都能将时间复杂度控制在O(nlog2n)O(n \cdot log_2n)的优化了,甚至进行两步分块,可以将时间复杂度降到O(n)O(n)。但是对于一些恶心的题目,仍然不够用,我们还可以再进一步优化。

持续更新中……