简介

本文先从狄利克雷卷积讲起，然后会简要介绍一种基于这一理论的有趣数论函数前缀和筛法（江湖人称 “杜教筛”）。

狄利克雷卷积

前面的博文中我们从初等数论的角度初步领略了莫比乌斯反演，是不是感觉推导有一些小复杂…… 但是，如果我们从抽象代数的角度来对其进行研究，就会发现反演这一公式自然而又优雅。

定义

我们研究的对象是诸如欧拉函数 φ\varphi 、莫比乌斯函数 μ\mu 等等的数论函数 (arithmetic function)。在此我们不妨把数论函数定义为 Z+⟼C\mathbb{Z}_{+} \longmapsto \mathbb{C} 的函数（正整数集合映射至复数集）。

定义： 对于数论函数 f,gf, g ，定义其 狄利克雷卷积 (Dirichlet convolution)：

(f⋅g)(n)=∑d∣nf(d)g(nd) (f \cdot g)(n) = \sum\limits_{d \mid n} f(d)g(\frac{n}{d})

注：后文常把 (f⋅g)(n)(f \cdot g)(n) 简写为 f⋅gf \cdot g 。

构造一个环

定理：记 F\mathbb{F} 为全体数论函数构成的集合，则 ⟨F,+,⋅⟩\langle \mathbb{F}, +, \cdot \rangle 构成可交换环。其中 ++ 就是正常的加法，⋅\cdot 则为刚刚提到的卷积（后文中可能会将其称作“乘法”）。

证明：

首先我们可以列一个证明清单：

  1. 运算的封闭性；
  2. ++ ：交换律、结合律；存在零元（零函数 0(n)=00(n) = 0 ，简记为 00 ）、负元；
  3. ⋅\boldsymbol{\cdot} ：交换律，结合律；存在单位元（元函数 ϵ(n)=n\epsilon(n) = n ，简记为 ϵ\epsilon ）；
  4. ++ 和 ⋅\cdot 间满足分配律。

第 1,21, 2 点中的内容较为显然，这里就略去证明了。下面对 3,43, 4 进行简要证明：

  • 乘法交换律：

    f⋅g=∑d∣nf(d)g(nd)let k=nd, ∴d=nk=∑k∣nf(nk)g(k)=g⋅f \begin{aligned} f \cdot g & = \sum\limits_{d | n}f(d)g(\frac{n}{d}) \\ & \text{let } k = \frac{n}{d}, \ \therefore d = \frac{n}{k} \\ & = \sum\limits_{k \mid n}f(\frac{n}{k})g(k) \\ & = g \cdot f \end{aligned}

  • 乘法结合律：

    (f⋅g)⋅h=∑t∣n[∑d∣tf(d)g(td)]h(nt)=∑t∣n∑d∣tf(d)g(td)h(nt) \begin{aligned} (f \cdot g) \cdot h & = \sum\limits_{t \mid n}\left[\sum\limits_{d \mid t} f(d)g(\frac{t}{d})\right]h(\frac{n}{t}) \\ & = \sum\limits_{t \mid n}\sum\limits_{d \mid t} f(d)g(\frac{t}{d})h(\frac{n}{t}) \end{aligned}

    f⋅(g⋅h)=∑d∣nf(d)[∑t∣ndg(t)h(ndt)]let T=dt=∑d∣nf(d)[∑T∣ng(Td)h(nT)]=∑T∣n∑d∣Tf(d)g(Td)h(nT) \begin{aligned} f \cdot (g \cdot h) & = \sum\limits_{d \mid n} f(d) \left[ \sum\limits_{t \mid \frac{n}{d}} g(t)h(\frac{n}{dt}) \right] \\ & \text{let } T = dt \\ & = \sum\limits_{d \mid n} f(d) \left[ \sum\limits_{T \mid n} g(\frac{T}{d})h(\frac{n}{T}) \right] \\ & = \sum\limits_{T \mid n}\sum\limits_{d \mid T} f(d)g(\frac{T}{d})h(\frac{n}{T}) \end{aligned}

    ∴(f⋅g)⋅h=f⋅(g⋅h) \therefore (f \cdot g) \cdot h = f \cdot (g \cdot h)

  • 加法和乘法间的分配律（由于已经证明交换律，因此只证左分配律）：

    f⋅(g+h)=∑d∣nf(d)[g(nd)+h(nd)]=∑d∣nf(d)g(nd)+f(d)h(nd)=f⋅g+f⋅h \begin{aligned} f \cdot (g + h) & = \sum\limits_{d \mid n} f(d) \left[ g(\frac{n}{d}) + h(\frac{n}{d}) \right] \\ & = \sum\limits_{d \mid n} f(d)g(\frac{n}{d}) + f(d)h(\frac{n}{d}) \\ & = f \cdot g + f \cdot h \end{aligned}

Voilà! 于是我们便得到了一个可交换环。我们来看看用它能够发现哪些有趣的事情~

有趣的性质

定义：若数论函数 ff 满足 f(1)=1f(1) = 1 ，且 ∀a,b  s.t.  a⊥b\forall a,b \ \text{ s.t. } \ a \perp b （若 a,ba, b 互质）满足 f(ab)=f(a)f(b)f(ab) = f(a)f(b) ，则称 ff 为 积性函数 (multiplicative function)。

定理：若 f,gf, g 为积性函数，则 f⋅gf \cdot g 也为积性函数。

证明：

∀a,b∈Z+, s.t. a⊥b\forall a, b \in \mathbb{Z}_{+}, \text{ s.t. } a \perp b ，有：

{f(ab)=f(a)f(b)g(ab)=g(a)g(b) \begin{cases} f(ab) & = f(a)f(b) \\ g(ab) & = g(a)g(b) \end{cases}

(f⋅g)(a)(f⋅g)(b)=∑t1∣af(t1)g(at1)∑t2∣bf(t2)g(bt2)=∑t1∣a∑t2∣bf(t1)f(t2)g(at1)g(bt2)∵a⊥b, ∴t1⊥t2, at1⊥bt2=∑t1∣a∑t2∣bf(t1t2)g(abt1t2)let d=t1t2=∑d∣abf(d)g(abd)=(f⋅g)(ab) \begin{aligned} (f \cdot g)(a) (f \cdot g)(b) & = \sum\limits_{t_1 \mid a}f(t_1)g(\frac{a}{t_1})\sum\limits_{t_2 \mid b}f(t_2)g(\frac{b}{t_2}) \\ & = \sum\limits_{t_1 \mid a}\sum\limits_{t_2 \mid b}f(t_1)f(t_2)g(\frac{a}{t_1})g(\frac{b}{t_2}) \\ & \because a \perp b, \ \therefore t_1 \perp t_2, \ \frac{a}{t_1} \perp \frac{b}{t_2} \\ & = \sum\limits_{t_1 \mid a}\sum\limits_{t_2 \mid b}f(t_1t_2)g(\frac{ab}{t_1t_2}) \\ & \text {let } d = t_1t_2\\ & = \sum\limits_{d | ab}f(d)g(\frac{ab}{d}) \\ & = (f \cdot g)(ab) \end{aligned}

对最后一步进行一个补充说明，本质上是 ∑t1∣a∑t2∣b1=∑t∣ab1\sum\limits_{t_1 \mid a}\sum\limits_{t_2 \mid b} 1 = \sum\limits_{t | ab}1 。不妨令 t1t_1 的质因子集合为 S1S_1 ，t2t_2 的质因子集合为 S2S_2 ，则 ∵t1⊥t2, ∴S1∩S2=Φ\because t_1 \perp t_2, \ \therefore S_1 \cap S_2 = \Phi 。因此，∀t∣ab\forall t \mid ab ，一定存在唯一的 t1,t2t_1, t_2 满足 t=t1t2t = t_1t_2 且 t1⊥t2t_1 \perp t_2 （可用反证法容易得证）。

再谈莫比乌斯反演？

我们再回过头来看看 μ\mu 的一个重要性质：

∑d∣nμ(d)={1n=10otherwise \sum\limits_{d \mid n} \mu(d) = \begin{cases} 1 & n = 1\\ 0 & \text{otherwise} \\ \end{cases}

如果我们定义一个数论函数 1(n)=11(n) = 1 ，并且简记为 11 ，那么我们可以将这一性质借助狄利克雷卷积表示为（其中 ϵ\epsilon 为我们之前定义的单位元）：

μ⋅1=ϵ \mu \cdot 1 = \epsilon

那么，如果有 f(n)=∑d∣ng(d)f(n) = \sum\limits_{d \mid n}g(d) ，即：

f=g⋅1⇒f⋅μ=g⋅1⋅μ⇒f⋅μ=g⋅(1⋅μ)⇒f⋅μ=g⋅(μ⋅1)⇒f⋅μ=g⋅ϵ⇒f⋅μ=g \begin{aligned} f = g \cdot 1 & \Rightarrow f \cdot \mu = g \cdot 1 \cdot \mu \\ & \Rightarrow f \cdot \mu = g \cdot (1 \cdot \mu) \\ & \Rightarrow f \cdot \mu = g \cdot (\mu \cdot 1) \\ & \Rightarrow f \cdot \mu = g \cdot \epsilon \\ & \Rightarrow f \cdot \mu = g \end{aligned}

于是我们得到了莫比乌斯反演：

g(n)=∑d∣ng(d)μ(nd) g(n) = \sum\limits_{d \mid n}g(d)\mu(\frac{n}{d})

在引入了数论函数和卷积构成的代数结构后，这一证明看起来无比简单明了、清新自然~

既然提到了莫比乌斯函数 μ\mu ，我们也不能忘了跟他一样经常出现的好基友欧拉函数 φ\varphi 。我们知道欧拉函数有一个性质：

∑d∣nφ(d)=n \sum\limits_{d \mid n} \varphi(d) = n

我们定义一个数论函数 N(n)=nN(n) = n ，并试着将上式表示成狄利克雷卷积？

φ⋅1=N \varphi \cdot 1 = N

我们试着对其操作一下：

φ⋅1=N⇒φ⋅1⋅μ=N⋅μ⇒φ=N⋅μ \begin{aligned} \varphi \cdot 1 = N & \Rightarrow \varphi \cdot 1 \cdot \mu = N \cdot \mu \\ & \Rightarrow \varphi = N \cdot \mu \end{aligned}

于是我们再次发现了两者之间非同一般的关系：

∑d∣nμ(d)d=φ(n)n \sum\limits_{d \mid n} \frac{\mu(d)}{d} = \frac{\varphi(n)}{n}

另外，除数函数也可以用狄利克雷卷积表示：

d(n)=∑d∣n1⇒d=1⋅1σ(n)=∑d∣nd⇒σ=N⋅1 \begin{aligned} d(n) = \sum\limits_{d \mid n}1 & \Rightarrow d = 1 \cdot 1 \\ \sigma(n) = \sum\limits_{d \mid n}d & \Rightarrow \sigma = N \cdot 1 \end{aligned}

杜教筛

杜教筛之所以有趣，并不是因为其具有怎样的普适性，而是其本身就在于 “构造”。只要能构造出来，我们就可以对特定的积性函数 ff 求出其前缀和 S(n)=∑i=1nf(i)S(n) = \sum\limits_{i = 1}^{n} f(i) 。

构造？

构造两个积性函数 g,h  s.t. h=f⋅gg, h \ \text{ s.t. } h = f \cdot g ：

∑i=1nh(i)=∑i=1n∑d∣if(d)g(id)=∑d=1ng(d)∑d∣if(id)=∑d=1ng(d)∑i=1⌊nd⌋f(i)=∑d=1ng(d)S(⌊nd⌋) \begin{aligned} \sum\limits_{i = 1}^{n} h(i) & = \sum\limits_{i = 1}^{n} \sum\limits_{d \mid i} f(d)g(\frac{i}{d}) \\ & = \sum\limits_{d = 1}^{n} g(d) \sum\limits_{d \mid i} f(\frac{i}{d}) \\ & = \sum\limits_{d = 1}^{n} g(d) \sum\limits_{i = 1}^{\left\lfloor \frac{n}{d} \right\rfloor} f(i) \\ & = \sum\limits_{d = 1}^{n}g(d) S(\left\lfloor \frac{n}{d} \right\rfloor) \end{aligned}

整理一下可得：

g(1)S(n)=∑i=1nh(i)−∑d=2ng(d)S(⌊nd⌋) g(1)S(n) = \sum\limits_{i = 1}^{n}h(i) - \sum\limits_{d = 2}^{n} g(d)S(\left\lfloor\frac{n}{d}\right\rfloor)

这就是杜教筛的本体。换句话说，只要我们构造出的 ∑i=1nh(i)\sum\limits_{i = 1}^{n}h(i) 是可以 O(1)\mathcal{O}(1) 求得的，那么结合适当的预处理和记忆化（预处理规模 O(n23)\mathcal{O}(n ^ \frac{2}{3}) ），我们可以用 O(n23)\mathcal{O}(n ^ \frac{2}{3}) 的复杂度计算出 S(n)S(n) 。

更具体地说，即我们应当先用线性筛预处理出前 O(n23)\mathcal{O}(n ^ \frac{2}{3}) 左右的前缀和，然后对于大于这一阈值的前缀和递归求解。同时，每当求出一个值我们将其记忆化在哈希表里以加速未来的运算。

对于这一筛法复杂度的详细证明大家可以参考这篇博文：杜教筛时间复杂度证明 - _Ark

应用

下面我们来看几点应用，感受一下杜教筛的魅力所在~

  • f(i)=φ(i), S(n)=∑i=1nφ(i)f(i) = \varphi(i), \ S(n) = \sum\limits_{i = 1}^{n} \varphi(i) ：

    由 φ⋅1=N\varphi \cdot 1 = N （对应 f⋅g=hf \cdot g = h ）：

    S(n)=∑i=1ni−∑d=2nS(⌊nd⌋) S(n) = \sum\limits_{i = 1}^{n}i - \sum\limits_{d = 2}^{n} S(\left\lfloor \frac{n}{d} \right\rfloor)

  • f(i)=μ(i), S(n)=∑i=1nμ(i)f(i) = \mu(i), \ S(n) = \sum\limits_{i = 1}^{n} \mu(i) ：

    由 μ⋅1=ϵ\mu \cdot 1 = \epsilon （对应 f⋅g=hf \cdot g = h ）：

    S(n)=1−∑d=2nS(⌊nd⌋) S(n) = 1 - \sum\limits_{d = 2}^{n} S(\left\lfloor \frac{n}{d} \right\rfloor)

  • f(i)=iφ(i), S(n)=∑i=1niφ(i)f(i) = i \varphi(i), \ S(n) = \sum\limits_{i = 1}^{n} i \varphi(i) ：

    h=f⋅g=∑d∣nf(d)g(nd)=∑d∣ndφ(d)g(nd)let g=N=n∑d∣nφ(d)=n2 \begin{aligned} h= f \cdot g & = \sum\limits_{d \mid n}f(d)g(\frac{n }{d}) \\ & = \sum\limits_{d \mid n} d \varphi(d)g(\frac{n}{d}) \\ & \text{let } g = N \\ & = n\sum\limits_{d \mid n}\varphi(d) \\ & = n^2 \end{aligned}

    S(n)=∑i=1ni2−∑d=2ndS(⌊nd⌋) S(n) = \sum\limits_{i = 1}^{n}i^2 - \sum\limits_{d = 2}^{n} dS(\left\lfloor \frac{n}{d} \right\rfloor)

  • f(i)=i2φ(i), S(n)=∑i=1ni2φ(i)f(i) = i^2 \varphi(i), \ S(n) = \sum\limits_{i = 1}^{n} i^2 \varphi(i) ：

    h=f⋅g=∑d∣nf(d)g(nd)=∑d∣nd2φ(d)g(nd)let g=N2=n2∑d∣nφ(d)=n3 \begin{aligned} h = f \cdot g & = \sum\limits_{d \mid n} f(d)g(\frac{n}{d}) \\ & = \sum\limits_{d \mid n}d^2\varphi(d)g(\frac{n}{d}) \\ & \text{let } g = N^2 \\ & = n^2\sum\limits_{d \mid n} \varphi(d) \\ & = n^3 \end{aligned}

    S(n)=∑i=1ni3−∑d=2nd2S(⌊nd⌋) S(n) = \sum\limits_{i = 1}^{n}i^3 - \sum\limits_{d = 2}^{n}d^2S(\left\lfloor \frac{n}{d} \right\rfloor)

至于具体的代码，大家可以去试试 洛谷 P4213: 杜教筛 (Sum)，顺便提供 我的代码 供参考。

完结撒花~

%%%