【Day 2】数论基础知识复习

参考博客:
莫比乌斯函数
杜教筛

一、欧拉函数

参见欧拉函数

二、狄利克雷卷积

对于两个数论函数 $f$ 和 $g$ ,他们的狄利克雷卷积

三、莫比乌斯反演

将上面的 $d | n$ 换成 $n|d$ , 就是莫比乌斯反演的第二种形式

$用卷积的角度来看$,就是

所以

因为

所以

四、杜教筛(搬运)

目标 : 求 $\sum_{i = 1}^{n}f(i)$
构造函数 $g$ 和 $h$ , 使得 $h = f * g$

接着,我们将右边式子的第一项给提出来,可以得到:

  • 这就是杜教筛的惯用套路式。经各种分析,只要当你的 $h(i)$ 的前缀和很好求,能在较短的时间内求出,那么当我们对后面的式子进行整除分块时,求$S(n)$的复杂度为$O(n^{\dfrac23})$
  • 当我们知道了这个套路式后,可能会思考,我们应该如何选择这个 $g$ 与 $h$ 呢?
  • 对于这个疑问,我没有太好的回答。只能说,依靠平时对于狄利克雷卷积中的各种式子的熟悉,以及仔细观察式子的能力啦!