目录
  1. 1. 写在前面
  2. 2. 前置知识
    1. 2.1. 积性函数
      1. 2.1.1. 定义
      2. 2.1.2. 性质
      3. 2.1.3. 常见的积性函数
    2. 2.2. 狄利克雷卷积
      1. 2.2.1. 定义
      2. 2.2.2. 性质
      3. 2.2.3. 一些例子
    3. 2.3. 莫比乌斯函数
      1. 2.3.1. 定义
      2. 2.3.2. 性质
      3. 2.3.3. 线性筛
  3. 3. 莫比乌斯反演
    1. 3.1. 定义
    2. 3.2. 证明
  4. 4. 一些应用
    1. 4.1. 简单例子:推导欧拉函数
    2. 4.2. 简单例子扩展
    3. 4.3. 另一个简单例子:求最大公约数的和
    4. 4.4. 扩展:求最小公倍数的和
    5. 4.5. 再扩展:二维最小公倍数求和
[算法]浅谈莫比乌斯反演

写在前面

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

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

  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)。但是对于一些恶心的题目,仍然不够用,我们还可以再进一步优化。

持续更新中……

文章作者: Jeson Vendetta Xie
文章链接: http://jvxie.com/2019/09/05/算法-莫比乌斯反演学习笔记/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 JVxie's Blog
打赏
  • 微信
  • 支付宝

评论