蒟蒻我在莫比乌斯反演学习笔记里留下了几个坑，于是开始漫长的填坑路。

狄利克雷卷积学习笔记

前置知识1：数论函数

什么是数论函数呢？数论函数指定义域为正整数，陪域为复数的函数。

以下知识中涉及到的函数大部分为数论函数

前置知识2：积性函数

积性函数是数论函数中很重要的一类。

对于函数 $f$ ，若 $\forall a, b\ (gcd(a,b) = 1)$ 都有 $f(ab) = f(a) \times f(b)$ ，则函数 $f$ 为积性函数。

另外的，若 $\forall a, b$ 都有 $f(ab) = f(a) \times f(b)$ ，则函数 $f$ 为完全积性函数。

常见的积性函数：

$\mu(x)$ ，莫比乌斯函数。这个函数我在莫比乌斯反演学习笔记中讲的挺清楚的（
$\varphi(x)$ ，欧拉函数。表示不大于 $x$ 且与 $x$ 互质的正整数个数，即 $\varphi(x) = \sum \limits_{i = 1}^{n} {[gcd(n, i) = 1]}$
$d(x)$ ，约数个数。表示 $x$ 的约数的个数，即 $d(x) = \sum \limits_{d|n} {1}$
$\sigma(x)$ ，约数和函数。表示 $x$ 的各个约数之和，即 $\sigma(x) = \sum \limits_{d|n} d$

常见的完全积性函数：

$\epsilon(x)$ ，元函数。 $\epsilon(x) = [x = 1]$
$I(x)$ ，恒等函数。 $I(x) = 1$
$N(x)$ ，单位函数。$N(x) = x$

什么是狄利克雷卷积

我们定义 $f$ ， $g$ 两个函数的狄利克雷卷积 $(*)$ 运算为：

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

我们把 $(f*g)$ 称为“ $f$ 卷 $g$ ”， $(n)$ 为范围（不写时默认范围为 $n$ ）。

很不显然，狄利克雷卷积满足一下运算规律：

交换律：
$f * g = g * f$
结合律：
$(f * g) * h = f * (g * h)$
分配律：
$(f + g) * h = f * h + g * h$

总之就和乘法是类似的，所以记忆方面并没有什么困难，然而这些运算律是可以证明的

交换律：很显然我们交换 $f$ 和 $g$ 仅仅是交换了枚举元素的顺序，对结果并没有影响；
结合律：很显然原式就是三个函数所有 $n$ 的约数项的和的乘积，那么无论先卷哪两个函数对结果都没有影响；
分配律：同样很显然，我们可以得到以下式子：

$\begin{align*} (f + g) * h &= \sum \limits_{d | n} {(f + g)(d)h(\frac{n}{d})}\\ &= \sum \limits_{d | n} {(f(d) + g(d))h(\frac{n}{d})}\\ &= \sum \limits_{d | n} {f(d)h(\frac{n}{d}) + g(d)h(\frac{n}{d})}\\ &= \sum \limits_{d | n} {f(d)h(\frac{n}{d})} + \sum \limits_{d | n} {g(d)h(\frac{n}{d})}\\ &= f * h + g * h \end{align*}$

解决完运算律之后，我们来看一下之前讲过的积性函数。

首先是元函数 $\epsilon$ ，所谓元函数，指的就是在狄利克雷卷积中充当单位元的作用，即有 $f * \epsilon = f$ 。

然后，狄利克雷卷积有一个非常重要的性质：如果 $f$ 和 $g$ 均为积性函数，那么 $f * g$ 一定也为积性函数。

用卷积的眼光看其他函数

莫比乌斯函数

（开始填坑）

在莫比乌斯反演笔记中，我们提到了莫比乌斯函数的几个性质，现在我们再来看一下它们。

关于莫比乌斯函数的重要等式

对于 $\forall n$ ， $\sum \limits_{d|n} {\mu(d)} = [n =1]$ ；

我们将这个式子写成卷积的形式可以得到在卷积中的一个重要等式：

$\mu * I = \epsilon$

利用这个式子，我们可以证明其他的东西。

莫比乌斯反演定理的证明

是不是觉得用定义证明莫比乌斯反演定理的时候的和式变换相当的麻烦呐？这里就给出一种相当简单的证明方法：

$f(n) = \sum \limits_{d | n} {g(d)}$

将上式写成卷积的形式：

$f = g * I$

两边同时卷上 $\mu$ ：

$f * \mu = g * I * \mu$

又因为有 $\mu * I = \epsilon$ 所以有：

$f * \mu = g * \epsilon = g$

即：

$g(n) = \sum \limits_{d | n} {\mu(d)f(\frac{n}{d})}$

欧拉函数

欧拉函数的性质

欧拉函数有一个相当美妙的性质：

$\sum \limits_{d | n} {\varphi(d) = n}$

证明过程如下：

设 $n = \prod \limits_{i = 1}^{m} {p_i^{a_i}}$ ，由于欧拉函数是积性函数，有

$\sum \limits_{d | n} {\varphi(d)} = \sum \prod \limits_{i = 1}^{m} {\varphi(p_i^j)} (0 \leq j \leq a_i)$

因式分解，上式等价于

$\prod \limits_{i = 1}^{m} {(\sum \limits_{j = 0}^{a_i} {\varphi(p_i^j)})} = \prod \limits_{i = 1}^{m} {(\sum \limits_{j = 0}^{a_i} {(p_i^j - p_i^{j - 1}) + 1})} = \prod \limits_{i = 1}^{m} {p_i^{a_i}} = n$

命题得证。

莫比乌斯函数与欧拉函数的关系

将欧拉函数的性质写成卷积形式：

$\varphi * I = N$

同样的，将等式两边同时卷上一个 $\mu$ ，得到：

$\varphi * I * \mu = N * \mu$

同样得到 $\varphi = N * \mu$ ，展开：

$\varphi(n) = \sum \limits_{d | n} {\mu(d) \times \frac{n}{d}}$

将两边同时除以 $n$

$\frac{\varphi(n)}{n} = \sum \limits_{d | n} {\frac{\mu(d)}{d}}$

于是得证。

总结

坑终于填的差不多了，累死本鸽子了咕咕咕（

然后，老师也说得好：数学是物理OI的工具，狄利克雷卷积也充当了一种工具的作用，在解决许多实际问题的时候有这工具总比没有要简单许多。

实际上可以看出来，有的时候利用好了数学的工具会使得本来相当麻烦的证明过程变得很简单，所以说还是要熟悉它们。

然后，下一个坑是：杜教筛！（立flag.jpg）