【算法】从狄利克雷卷积到莫比乌斯反演再到杜教筛 ——quhengyi11

这篇文章是用来复习莫比乌斯反演，可能对新学不是那么友好。

然而如果你熟练莫比乌斯反演的话这里的杜教筛教程也是可以看看的啦（我就是为了学杜教筛才去复习莫比乌斯反演的毕竟忘得差不多了 QAQ）

最近一直在肝这篇文章和 yyb 那篇 blog(后者用掉好几节数学课 (雾

狄利克雷卷积:

$$(f*g)(n)=\sum_{d|n}f(d)g(\frac n d)$$

我们规定几个函数

$$1(n) = 1$$
$$e(n)=[n == 1]$$
$$Id(n) = n$$

我们有以下结论

$$(1*u)(n)=\sum_{d|n}\mu(d)=e(n)$$

这个结论想必你在学莫比乌斯反演的时候就已经搞懂了，$n=1$的时候显然，$n>1$的时候就是一个 $(1-1)^k$的二项式展开，其中 $k$表示 $n$质因子个数

$$(\mu*Id)(n) = \sum_{d|n}\frac n d \mu (d)=\phi(n)$$
这个也很简单，你会惊奇地发现这不就是 $\phi(n)$的计算式喵…

$$(1*\phi)(n)=\sum_{d|n}\phi(d)=Id(n)$$

优美的证明：

$$1*\phi = 1 * \mu * Id = e * Id = Id$$

(狄利克雷卷积有交换律结合律就不用说了，很显然的，如果想看的去文章最下面参考资料中戳 snakes 的那篇文章就行)

---

莫比乌斯反演

1

$n\leq m$，求
$$\sum_{i=1}^n\sum_{j=1}^m [gcd(i,j)==1]$$
令
$$f(x)=\sum_{i=1}^n\sum_{j=1}^m [gcd(i,j)==x]$$
所求即为 $f(1)$

令
$$g(x)=\sum_{x|d}f(d)$$
由莫比乌斯反演基础柿子
$$f(x)=\sum_{x|d}\mu(d)g(\frac d x)$$
则
$$f(1)=\sum_{d=1}^n \mu(d)g(d)$$
又因为
$$g(x)=\sum_{i=1}^n\sum_{j=1}^m[x|gcd(i,j)]=\sum_{i=1}^{\frac n x}\sum_{j=1}^{\frac m x}1=[\frac n x][\frac m x]$$
所以 $g(x)$可以 $O(1)$计算

可以用数论分块将 $f(1)$的计算优化到 $O(\sqrt n)$

2

$n\leq m$，求
$$\sum_{i=1}^n\sum_{j=1}^mgcd(i,j)$$
上式等价于
$$\sum_{d=1}^nd\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)==d]$$
观察 $d$后面的式子，发现和结论 $1$的式子好像啊
$$\begin{align}\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)==d] &= \sum_{i=1}^{\frac n d}\sum_{j=1}^{\frac m d}[gcd(i,j)==1]
\\
&=\sum_{x=1}^{\frac n d} \mu(d)[\frac n {xd}][\frac m {xd}]
\end{align}
$$
带回原来的式子
$$
\sum_{d=1}^n\sum_{x=1}^{\frac n d} \mu(d)[\frac n {xd}][\frac m {xd}]
$$
注意一下，这里本质上是 $\frac {[\frac n d]}{x}$的可是这样写不好看所以就写成 $[\frac n {xd}]$了

upd: 后来 qhy 发现 $[\frac {[\frac n d]} x]=[\frac n {xd}]$，设带余方程可以轻松证明，但是 qhy 记得有一种放缩卡两边的证明方法等想起来再说吧 (取整函数那一堆好像都有类似的)，如果 qhy 这里一段时间没有再次 upd 的话记得催更 (准备养鸽巢)

upd：两边夹的方法我是没找到，但是还是补一个证明吧，这个东西挺重要的。

本质上是要证明

$$[\frac{[n]}{x}] = [\frac n x]$$

其中 $n$是实数，$x$是正整数。

假设

$$k=[\frac n x]$$

$$b={\frac n x}$$

(其中 ${x}$表示实数 $x$的小数部分)

那么

$$n=kx+bx$$

$$[n]=kx+[bx]$$

$$[\frac{[n]}x] = k + [\frac{[bx]}{x}]$$

因为
$$[bx] < [x] \leq x$$

因此

$$[\frac{[n]}x] = k$$

还有一种很妙的感性理解方法

$$[\frac x c]=\sum_{t}[0 < t \leq x \& \& c | t]$$

$$[\frac {[x]} c]=\sum_{t}[0 < t \leq [x] \& \& c | t]$$

因为 $t$是整数，上界由 $x$到 $[x]$的变化并不会影响 $t$的取值范围，因此两式等价。

qhy 注意！

这个式子的复杂度有点难分析，首先我们发现 $[\frac n d]$可以先进行一次数论分块，这个是显然的，$\frac {[\frac n d]}{x}$还能进行一次数论分块，由于 qhy 比较萌新不能感性理解数论分块套数论分块是个啥所以她需要再化一下式子。

令 $s$表示 $d$的当前分块的最小值，$mx$为最大值，这个块中满足 $[\frac n d]$和 $[\frac m d]$为定值

$$\sum_{i=s}^{mx}\mu(i) \sum_{x=1}^{\frac n s}[\frac {[\frac n s]}{x}][\frac {[\frac m s]}{x}]$$
前面的 $\mu$就是一个前缀和，很容易维护，下面可以丢掉

为了方便起见令 $a=[\frac n s]$，$b=[\frac m s]$
$$\sum_{x=1}^a[\frac a x][\frac b x]$$
又是熟悉的味道，我们用同样的设法也能将这个东西用数论分块搞掉

感性的理解就是，第一次分块的时候就是批量处理 $\mu(i)$的前缀和，第二次分块的时候就是批量处理 $1$的前缀和 (即乘一个块的大小)

upd: 其实有更感性的理解啊，你可以把后面那个式子看成一个二元函数 $f(x,y)$然后你就会发现求前面一个式子的前缀和的时候可以数论分块，算 $f(x,y)$内部的时候也可以数论分块 qwq

所以综上所述，这个式子的复杂度是 $O(n)$的

我们可以将它优化到 $O(\sqrt n)$

把那个式子再写一遍吧
$$
\sum_{d=1}^n\sum_{x=1}^{\frac n d} \mu(d)[\frac n {xd}][\frac m {xd}]
$$

注意到 $xd \leq n$，我们令 $T=xd$然后枚举 $T$试一试
$$\sum_{T=1}^n [\frac n T][\frac m T]\sum_{d|T}d\mu(\frac T d)$$
本质上就是一个交换枚举顺序所以不解释了

容易发现
$$\phi(T)=\sum_{d|T}d\mu(\frac T d)$$
即 $(\mu*Id)=\phi$

3

$n\leq m$，求
$$\sum_{i=1}^n \sum_{j=1}^m lcm(i,j)$$
原式等价于
$$\sum_{i=1}^n \sum_{j=1}^m \frac {ij}{gcd(i,j)}$$
根据套路
$$\sum_{d=1}^n \sum_{i=1}^n \sum_{j=1}^m\frac {ij}d [gcd(i,j)==d]$$
把 d 弄出来
$$\sum_{d=1}^n d\sum_{i=1}^{\frac n d} \sum_{j=1}^{\frac m d} ij [gcd(i,j)==1]$$
又是熟悉的味道，我们令 $x=[\frac n d ],y=[\frac m d]$
$$f(d)=\sum_{i=1}^{x} \sum_{j=1}^{y} ij[gcd(i,j)==d]$$
$$
\begin{align}
g(z)=\sum_{x|d}f(d)&=\sum_{i=1}^x\sum_{j=1}^y[z|gcd(i,j)]ij\\
&=z^2\sum_{i=1}^{\frac x z}\sum_{j=1}^{\frac y z}ij\\
&=z^2sum(1, \frac x z)sum(1, \frac y z)
\end{align}
$$
其中 $sum(x,y)$表示 $\sum_{i=x}^y i$

由莫比乌斯反演基础柿子
$$f(x)=\sum_{x|d}\mu(d)g(\frac d x)$$
$$f(1)=\sum_{d=1}^n\mu(d)d^2sum(1,\frac x d )sum(1, \frac y d)$$

数论分块一下 $O(\sqrt n)$美滋滋

但是你不要忘记你还要带回原式子啊喂
$$ans=\sum_{d=1}^n d \sum_{p = 1}^n \mu(p)p^2sum(1,\frac n {pd})sum(1, \frac m {pd})$$

类似的两次数论分块可以解决这个问题了啦

复杂度 $O(n)$

4

$n\leq m$，$d(x)$表示 $x$的约数个数和，求
$$\sum_{i=1}^n\sum_{j=1}^m d(i\times j)$$
首先我们先证明一个东西
$$d(x\times y)=\sum_{i|x}\sum_{j|y}[gcd(i,j)==1]$$
记
$$x = \prod p_i^{a_i} \quad y=\prod p_i^{b_i}$$
首先显然有
$$LHS=\prod(a_i+b_i+1)$$
而通过观察我们发现，$RHS$等价于 $\forall i \quad s.t.[a_i == 0||b_i==0]$

而如果只看当前的 $p_i$，$a_i==0$有 $b_i+1$种取法，$b_i==0$有 $a_i+1$种取法，去掉两个都是 $0$的情况，也就是说使得 $p_i|gcd(i,j)$为假命题的 $a_i$和 $b_i$的方案数为 $a_i+b_i+1$，因此有
$$RHS=\prod(a_i+b_i+1)=LHS$$
$Q.E.D.$

那么原式子我们可以化为
$$\sum_{i=1}^n\sum_{j=1}^m \sum_{x|i}\sum_{y|j} [gcd(x, y)==1]$$
有了 $gcd$就是莫比乌斯反演专场了

但是等等，你会发现这里的 $g$函数并不好求，其实我们这里可以再交换一下枚举顺序，枚举 $x,y$

$$\sum_{x=1}^n\sum_{y=1}^m\sum_{x|i}^{i\leq n}\sum_{y|j}^{j \leq m}[gcd(x,y)==1]$$
接着化简
$$\sum_{x=1}^n\sum_{y=1}^m[\frac n x][\frac m y][gcd(x,y)==1]$$
设
$$f(p)=\sum_{x=1}^n\sum_{y=1}^m[\frac n x][\frac m y][gcd(x,y)==p]$$
$$
\begin{align}
g(d)=\sum_{d|p}f(p)
&=\sum_{x=1}^n\sum_{y=1}^m[\frac n x][\frac m y][d|gcd(x,y)]\\
&=\sum_{x=1}^{\frac n d}\sum_{y=1}^{\frac m d}[\frac n {xd}][\frac m {yd}]\\
&=\sum_{x=1}^{\frac n d}[\frac n {xd}]\sum_{y=1}^{\frac m d}[\frac m {yd}]
\end{align}
$$
然后我 tm 就卡住了，其实我们可以预处理一个 $s(n)$
$$s(n)=\sum_{i=1}^n [\frac n i]$$
那样就有
$$g(d)=\frac {s(\frac n d)}{d} \times \frac {s(\frac m d)}{d}$$
你会发现 $s(n)$表示的就是 $1$到 $n$的约数个数和，所以你可以先线性筛出约数个数 $d(n)$然后再求前缀和即可，当然暴力的复杂度 $O(n\sqrt n)$一般也是可以接受的 (我指 [SDOI2015] 约数个数和那题)
$$ans=f(1)=\sum_{d=1}^n \mu(d)g(d)$$
数论分块 $O(\sqrt n)$解决

---

杜教筛

杜教？dyh？学不来学不来.jpg

虽然杜教是神仙但是杜教筛真心不难

首先杜教筛是求积性函数前缀和的也就是 $\sum_{i=1}^nf(i)$

这里我还是用一遍 yyb 的 blog 里面的那个栗子吧

$n\leq 10^9$，求
$$\sum_{i=1}^n\mu(i)$$

哇这咋整啊，难道设一个莫比乌斯反演里面的 $g$函数然后魔法容斥？但是我还是太 naive 了这是容斥不了的。

这时候我们聪明的杜教就给出了这样一种套路

设 $f(n)$，$g(n)$为积性函数

把它们卷积起来

$$(f*g)(n)=\sum_{d|n}f(d)g(\frac n d)$$

把卷积做前缀和

$$\sum_{i=1}^n\sum_{d|i}g(d)f(\frac i d)$$
注意到 $d$固定的时候，每次 $\frac i d$其实是一段连续的数，于是我们如是交换枚举顺序
$$\sum_{d=1}^n g(d)\sum_{i=1}^{\frac n d} f(i)$$
记
$$s(n)=\sum_{i=1}^nf(i)$$
则上式为
$$\sum_{d=1}^ng(d)s(\frac n d)$$
我们要求的是 $s(n)$，容易发现
$$g(1)s(n)=\sum_{d=1}^ng(d)s(\frac n d)-\sum_{d=2}^ng(d)s(\frac n d)$$
前面那一部分就是 $(f*g)(n)$，我们往往可以通过构造 $g$来快速算出这个值，具体怎么构造可以参考上面狄利克雷卷积的几个恒等式

后面的部分我们可以发现可以对 $\frac n d$进行数论分块也就是 $\sqrt n$的，然后你可以预处理一部分 $s(n)$(比如说 $n\leq 10^7$)，然后对于超过预处理范围的就再记忆化搜索就行，每次记搜里面要跑 $\sqrt n$次，记搜的次数是大概是 $1$到 $\frac n {10^7}$的质因子个数，显然是调和数列级别的，也就是说时间复杂度大概是 $O(\sqrt n \frac n {10^7}log\frac n {10^7})$
证明是乱糊的啦 QAQ 所以你会发现上面的文字里有很多个大概 QwQ，听说预处理的时候处理 $n^{\frac 2 3}$速度是坠块的啦（：

杜教筛题目另 (hai) 开 (mei) 文 (you) 章 (xie) 吧 (ya)

参考资料
yyb: 他肯定知道什么是” 莫比乌斯反演” 和” 杜教筛”

snakes:Möbius inversion and Dirichlet convolution