莫比乌斯函数

定义

莫比乌斯函数是一个数论函数，定义如下：

μ(n)={1,n=1(−1)k,n是k个不同质数的乘积0,n含有平方因子\mu(n)= \begin{cases} 1,\quad n=1 \\ (-1)^k,\quad \text{$n$是$k$个不同质数的乘积}\\ 0,\quad \text{$n$含有平方因子} \end{cases}

例如：

μ(1)=1,μ(2)=−1,μ(6)=1,μ(12)=0\mu(1)=1,\mu(2)=-1,\mu(6)=1,\mu(12)=0

性质

莫比乌斯函数是积性函数，也就是：

(m,n)=1⇒μ(mn)=μ(m)μ(n)(m,n)=1\Rightarrow \mu(mn)=\mu(m)\mu(n)

恒等式

下面的恒等式十分重要：

ϵ(n)=∑d∣nμ(n)={1,n=10,n>1\epsilon(n)=\sum_{d\mid n}\mu(n)= \begin{cases} 1,\quad n=1\\ 0,\quad n>1 \end{cases}

我们称 ϵ(n)\epsilon(n) 为单位函数
这个恒等式是符合直觉的：假设 nn 的不同质因子个数为 rr，从中挑选一个子集相乘就可以得到 nn 的一个因子 dd，所以：

  • 无平方因子有 2r2^r 个
  • 其中：
    • 2r−12^{r-1} 个具有偶数个质因子（μ=1\mu=1）
    • 2r−12^{r-1} 个具有奇数个质因子（μ=−1\mu=-1）

把它们加起来，结果为0。这说明了因子的“计数对称性”
这个恒等式有一个常见应用：

[i⊥j]=[(i,j)=1]=∑d∣(i,j)μ(d)=∑d[d∣i][d∣j]μ(d)[i\perp j]=[(i,j)=1]=\sum_{d\mid(i,j)}\mu(d)=\sum_d[d\mid i][d\mid j]\mu(d)

它将互素的条件转化为关于莫比乌斯函数的求和式，方便进一步推导

求法

如果只需要计算单个 nn 的莫比乌斯函数值 μ(n)\mu(n)，直接根据定义，对 nn 进行质因数分解即可，时间复杂度为 O(n)O(\sqrt{n})
当然，莫比乌斯函数是积性函数，可以利用线性筛求出 nn 以内的所有莫比乌斯函数值，时间复杂度为 O(n)O(n)

狄利克雷卷积

数论函数 f(n)f(n) 和 g(n)g(n) 的 狄利克雷卷积 ，记作 f∗gf*g，定义为数论函数

(f∗g)(n)=∑k∣nf(k)g(nk)=∑kl=nf(k)g(l)(f*g)(n)=\sum_{k\mid n}f(k)g(\frac{n}{k})=\sum_{kl=n}f(k)g(l)

单位函数 ϵ\epsilon 是莫比乌斯函数 μ\mu 和常数函数 11 的狄利克雷卷积：

ϵ=μ∗1⇔ϵ(n)=∑d∣nμ(d)\epsilon=\mu*1\Leftrightarrow \epsilon(n)=\sum_{d\mid n}\mu(d)

约数个数函数 rr 是常数函数 11 和它自身的狄利克雷卷积：

r=1∗1⇔r(n)=∑d∣n1r = 1*1 \Leftrightarrow r(n)=\sum_{d\mid n} 1

约数和函数 σ\sigma 是恒等函数 idid 和常数函数 11 的狄利克雷卷积：

σ=id∗1⇔σ(n)=∑d∣nd\sigma=id*1\Leftrightarrow \sigma(n)=\sum_{d\mid n}d

欧拉函数 ϕ\phi 是恒等函数 idid 和莫比乌斯函数 μ\mu 的狄利克雷卷积：

ϕ=id∗μ⇔ϕ(n)=∑d∣nd⋅μ(nd)\phi=id*\mu\Leftrightarrow \phi(n)=\sum_{d\mid n} d\cdot \mu(\frac{n}{d})

性质

狄利克雷卷积满足交换律、结合律、分配律，这里不一一证明。并且，如果把狄利克雷卷积看成一个数论函数上的二元关系，可以发现其单位元、零元和逆元：

  • 单位元：ϵ(n)\epsilon(n)，这是因为有 (f∗ϵ)(n)=∑d∣nf(d)ϵ(n/d)=f(n)(f*\epsilon)(n)=\sum_{d\mid n}f(d)\epsilon(n/d)=f(n)，因为只有 d=nd=n 时ϵ(n/d)=1\epsilon(n/d)=1，其余为0
  • 零元：全零函数 00
  • 逆元：数论函数 ff 的狄利克雷逆元 gg 满足 f∗g=ϵf*g=\epsilon，特别的，有 (f∗g)(1)=f(1)g(1)=1(f*g)(1)=f(1)g(1)=1，所以，ff 的狄利克雷逆元存在，当且仅当 f(1)≠0f(1)\ne 0

数论函数 ff 的狄利克雷函数的值是可以递推计算的，首先有：

g(1)=1f(1)g(1)=\frac{1}{f(1)}

接下来，当 n>1n>1 时：

(f∗g)(n)=∑d∣nf(d)g(nd)=ϵ(n)=0(f*g)(n)=\sum_{d\mid n}f(d)g(\frac{n}{d})=\epsilon(n)=0

将 dd 分成 1<d≤n1<d\le n 和 d=1d=1 两类，就有：

∑d∣n,1<d≤nf(d)g(nd)+f(1)g(n)=0\sum_{d\mid n,1<d\le n} f(d)g(\frac{n}{d})+f(1)g(n)=0

把 g(n)g(n) 解出来，就有：

g(n)=−∑d∣n,d≠1f(d)g(nd)f(1)g(n)=-\frac{\sum_{d\mid n,d\ne 1}f(d)g(\frac{n}{d})}{f(1)}

这样就可以递推求解了
同时易证：两个积性函数的狄利克雷卷积也是一个积性函数，这可以帮助我们判断形如 ∑d∣nf(d)g(nd)\sum_{d\mid n}f(d)g(\frac{n}{d}) 的积性，从而判断能否使用线性筛法

莫比乌斯反演

对于一些函数 f(n)f(n)，如果很难直接求出他的值，但是容易求出其倍数和或约数和 g(n)g(n)，那么就可以使用莫比乌斯反演简化计算
设 f,gf,g 是两个数论函数，则有：

f(n)=∑d∣ng(d)⇔g(n)=∑d∣nμ(nd)f(d)f(n)=\sum_{d\mid n}g(d)\Leftrightarrow g(n)=\sum_{d\mid n}\mu(\frac{n}{d})f(d)

写成狄利克雷卷积的形式，有：

f=1∗g⇔g=μ∗ff=1*g\Leftrightarrow g=\mu*f

这个证明是显然的，因为前面我们知道，单位函数 ϵ\epsilon 是莫比乌斯函数 μ\mu 和常数函数 11 的狄利克雷卷积，在左式两边同时对 μ\mu 做狄利克雷卷积，就有：

f∗μ=(1∗g)∗μ=(1∗μ)∗g=ϵ∗g=gf*\mu=(1*g)*\mu=(1*\mu)*g=\epsilon*g=g

欧拉函数 ϕ(n)\phi(n) 满足 n=∑d∣nϕ(d)n=\sum_{d\mid n}\phi(d)，即 id=1∗ϕid=1*\phi，对其反演得到 ϕ=μ∗id\phi=\mu*id，即

ϕ(n)=∑d∣ndμ(nd)\phi(n)=\sum_{d\mid n}d\mu(\frac{n}{d})

除数函数 σk(n)=∑d∣ndk\sigma_k(n)=\sum_{d\mid n}d^k，即 σk=1∗idk\sigma_k=1*id_k，对其反演得到 idk=μ∗σkid_k=\mu*\sigma_k，即

nk=∑d∣nμ(nd)σk(d)n^k=\sum_{d\mid n}\mu(\frac{n}{d})\sigma_k(d)

我们之前考虑的反演都是对于 nn 的某一因数 dd，当然也可以考虑其倍数：

f(n)=∑n∣dg(d)⇔g(n)=∑n∣dμ(dn)f(d)f(n)=\sum_{n\mid d}g(d)\Leftrightarrow g(n)=\sum_{n\mid d}\mu(\frac{d}{n})f(d)

证明略，这是显然的

狄利克雷前缀和

用处不大，了解一下就好
考虑基本的莫比乌斯反演关系：

f(n)=∑d∣ng(d)f(n)=\sum_{d\mid n}g(d)

假如说知道 {g(k)}k=1n\left \{ g(k)\right \}_{k=1}^n 的值，我们可以使用类似前缀和的方式来求出{f(k)}k=1n\left \{ f(k)\right \}_{k=1}^n 的值，只需要考虑因数 dd 对 f(k)f(k) 的贡献，将其累加起来即可
对于高维前缀和，我们有一种求法是：遍历所有的维度，并将每个位置的值都累加到该位置在该位置上的后继位置，在这个问题中，我们可以考虑每个素数 pp，和 pp 同维的位置有 2p,3p,…2p,3p,\dots，考虑到 npnp 时，只需要将 nn 处的函数值加到 npnp 处即可
这个遍历顺序和埃氏筛是一致的，因此我们可以在 O(nlog⁡log⁡n)O(n\log \log n) 的时间内计算出 {f(k)}k=1n\left \{ f(k)\right \}_{k=1}^n 的值，我们称其为狄利克雷前缀和

常见变形

gcd和lcm相关的变形

[(i,j)=k][(i,j)=k] 可以转化成 [(ik,jk)=1][(\frac{i}{k},\frac{j}{k})=1]，用莫比乌斯函数的性质就可以转化成 ∑d[d∣ik][d∣jk]μ(d)\sum_d[d\mid \frac{i}{k}][d\mid \frac{j}{k}]\mu(d)
例如，求下面式子的值：

f(n,m,k)=∑i=xn∑j=ym[(i,j)=k]f(n,m,k)=\sum_{i=x}^{n}\sum_{j=y}^{m}[(i,j)=k]

做如下变换：

f(n,m,k)=∑i=xn∑j=ym[(i,j)=k]=∑i=⌈xk⌉⌊nk⌋∑j=⌈yk⌉⌊mk⌋[(i,j)=1]=∑i=⌈xk⌉⌊nk⌋∑j=⌈yk⌉⌊mk⌋∑d[d∣i][d∣j]μ(d)=∑dμ(d)∑i=⌈xk⌉⌊nk⌋[d∣i]∑j=⌈yk⌉⌊mk⌋[d∣j]=∑dμ(d)(⌊⌊nk⌋d⌋−⌊⌈xk⌉−1d⌋)(⌊⌊mk⌋d⌋−⌊⌈yk⌉−1d⌋)\begin{aligned} f(n,m,k)&=\sum_{i=x}^{n}\sum_{j=y}^{m}[(i,j)=k] \\ &=\sum_{i=\left \lceil \frac{x}{k} \right \rceil }^{\left \lfloor \frac{n}{k} \right \rfloor }\sum_{j=\left \lceil \frac{y}{k} \right \rceil}^{\left \lfloor \frac{m}{k} \right \rfloor }[(i,j)=1] \\ &=\sum_{i=\left \lceil \frac{x}{k} \right \rceil }^{\left \lfloor \frac{n}{k} \right \rfloor }\sum_{j=\left \lceil \frac{y}{k} \right \rceil}^{\left \lfloor \frac{m}{k} \right \rfloor }\sum_d[d\mid i][d\mid j]\mu(d) \\ &=\sum_d\mu(d)\sum_{i=\left \lceil \frac{x}{k} \right \rceil }^{\left \lfloor \frac{n}{k} \right \rfloor }[d\mid i]\sum_{j=\left \lceil \frac{y}{k} \right \rceil}^{\left \lfloor \frac{m}{k} \right \rfloor }[d\mid j] \\ &=\sum_d\mu(d)(\left \lfloor \frac{\left \lfloor \frac{n}{k} \right \rfloor }{d} \right \rfloor-\left \lfloor \frac{\left \lceil \frac{x}{k} \right \rceil -1}{d} \right \rfloor)(\left \lfloor \frac{\left \lfloor \frac{m}{k} \right \rfloor }{d} \right \rfloor-\left \lfloor \frac{\left \lceil \frac{y}{k} \right \rceil -1}{d} \right \rfloor) \end{aligned}

推导的过程运用了莫比乌斯函数的性质，以及区间内倍数个数的计算（容斥原理）
这个公式接下来可以把后面的两个括号拆开在展开整理一下，能够得到四项，其中每一项都是如下的乘积形式：

∑dμ(d)⌊Ud⌋⌊Vd⌋\sum_d\mu(d)\left \lfloor \frac{U}{d} \right \rfloor \left \lfloor \frac{V}{d} \right \rfloor

只需要线性筛一下莫比乌斯函数，求一下前缀和，就可以使用数论分块来求解这个式子，对于原式只需要进行四个值的组合即可，时间复杂度为 O(N+N)O(N+\sqrt{N})

求下面式子的值：

S(n)=∑i=1nlcm(i,n)S(n)=\sum_{i=1}^n\text{lcm}(i,n)

首先，先转化成gcd；

S(n)=∑i=1nin(i,n)=n∑i=1ni(i,n)\begin{aligned} S(n)&=\sum_{i=1}^n\frac{in}{(i,n)} \\ &=n\sum_{i=1}^n\frac{i}{(i,n)} \end{aligned}

设 d=(i,n)d = (i,n)，那么每个 ii 必须写成 i=dji=dj，则有 (j,nd)=1(j,\frac{n}{d})=1，代回去得：

S(n)=n∑d∣n∑1≤j≤ndj[(j,nd)=1]S(n)=n\sum_{d\mid n}\sum_{1\le j\le \frac{n}{d}}j[(j,\frac{n}{d})=1]

注意到 ∑1≤j≤ndj[(j,nd)=1]\sum_{1\le j\le \frac{n}{d}}j[(j,\frac{n}{d})=1] 表示 [1,nd][1,\frac{n}{d}] 中与 nd\frac{n}{d} 互质的数的和，自然联想到欧拉函数 ϕ\phi，当 nd>1\frac{n}{d}>1 时，ϕ(nd)\phi(\frac{n}{d}) 总是偶数，这是因为假如 i⊥ndi\perp \frac{n}{d}，那么 nd−i⊥nd\frac{n}{d}-i\perp \frac{n}{d}，它们是成对出现的，并且它们的和为 nd\frac{n}{d}，故原式转化为：

S(n)=n∑d∣nϕ(nd)nd2=n∑d∣nϕ(d)d2S(n)=n\sum_{d\mid n}\frac{\phi(\frac{n}{d})\frac{n}{d}}{2}=n\sum_{d\mid n}\frac{\phi(d)d}{2}

接下来线性筛一下欧拉函数即可

求下面表达式的值：

f(n,m)=∑i=1n∑j=1mlcm(i,j)f(n,m)=\sum_{i=1}^n\sum_{j=1}^{m}\text{lcm}(i,j)

依旧lcm转化成gcd，得到：

f(n,m)=∑i=1n∑j=1mij(i,j)=∑i=1n∑j=1m∑kijk[(i,j)=k]=∑i=1⌊nk⌋∑j=1⌊mk⌋∑kkij[(i,j)=1]=∑i=1⌊nk⌋∑j=1⌊mk⌋∑kkij∑d[d∣i][d∣j]μ(d)=∑kk∑dμ(d)(∑i=1⌊nk⌋i[d∣i])(∑j=1⌊mk⌋j[d∣j])\begin{aligned} f(n,m)&=\sum_{i=1}^n\sum_{j=1}^m\frac{ij}{(i,j)} \\ &=\sum_{i=1}^n\sum_{j=1}^m\sum_{k}\frac{ij}{k}[(i,j)=k] \\ &=\sum_{i=1}^{\left \lfloor \frac{n}{k} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{m}{k} \right \rfloor}\sum_kkij[(i,j)=1] \\ &=\sum_{i=1}^{\left \lfloor \frac{n}{k} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{m}{k} \right \rfloor}\sum_kkij\sum_d[d\mid i][d\mid j]\mu(d) \\ &=\sum_kk\sum_d\mu(d)(\sum_{i=1}^{\left \lfloor \frac{n}{k} \right \rfloor}i[d\mid i])(\sum_{j=1}^{\left \lfloor \frac{m}{k} \right \rfloor}j[d\mid j]) \end{aligned}

对于后面的两个式子，显然有：

∑i=1⌊nk⌋i[d∣i]=d∑i=1⌊⌊nk⌋d⌋i=⌊⌊nk⌋d⌋(⌊⌊nk⌋d⌋+1)d2\begin{aligned} \sum_{i=1}^{\left \lfloor \frac{n}{k} \right \rfloor}i[d\mid i]&=d\sum_{i=1}^{\left \lfloor \frac{\left \lfloor \frac{n}{k} \right \rfloor}{d} \right \rfloor} i \\ &=\frac{\left \lfloor \frac{\left \lfloor \frac{n}{k} \right \rfloor}{d} \right \rfloor(\left \lfloor \frac{\left \lfloor \frac{n}{k} \right \rfloor}{d} \right \rfloor+1)d}{2} \end{aligned}

可知后面两个式子可以数论分块计算，但是我们需要知道前面两个和式的前缀和，令 G(n)=n(n+1)2G(n)=\frac{n(n+1)}{2}，做换元 l=kdl=kd，式子化为：

f(n,m)=∑ll∑d∣lμ(d)dG(⌊nl⌋)G(⌊ml⌋)\begin{aligned} f(n,m)&=\sum_ll\sum_{d\mid l}\mu(d)dG(\left \lfloor \frac{n}{l} \right \rfloor)G(\left \lfloor \frac{m}{l} \right \rfloor) \end{aligned}

发现函数 F(l)=l∑d∣lμ(d)dF(l)=l\sum_{d\mid l}\mu(d)d 是积性函数，可以直接线性筛并求出它的前缀和，然后就可以使用数论分块计算 f(n,m)f(n,m) 的值了