初等数论学习笔记 III：数论函数与筛法( 三 ) _生活百科

证明：\((\epsilon * f)(n) = \sum\limits_{d \mid n}[d = 1]f\left(\dfrac n d\right) = f(n)\) 。证毕。
因此单位函数 \(\epsilon\) 为狄利克雷卷积的单位元。
既然存在单位元，就可以据此定义数论函数 \(f\) 的逆元 \(f ^ {-1}\)，满足 \(f * f ^ {-1} = \epsilon\) 。

性质 3：\(f\) 可逆当且仅当 \(f(1)\neq 0\) 。

证明：设 \(g = f ^ {-1}\) 。当 \(f(1) = 0\) 时，\(f(1)g(1) = 0\) 且 \(f(1) g(1) = \epsilon(1) = 1\)，矛盾。当 \(f(1) \neq 0\) 时，\(g(1) = \dfrac 1 {f(1)}\) ，对 \(n > 1\) 的 \(g(x)\) 通
过 \(\sum\limits_{d\mid x} g(d)f\left(\dfrac n d\right) = 0\) 得到递推式 \(g(n) = -\dfrac{\sum\limits_{d \mid n, d \neq n} g(d)f\left(\dfrac n d\right)} {f(1)}\) 。这同时说明逆元唯一。证毕。

性质 4：\(f = g\) 的充要条件是 \(f * h = g * h\)，其中 \(h(1) \neq 0\) 。

证明：\(f * h = g * h\Rightarrow f * h * h ^ {-1} = g * h * h ^ {-1} \Rightarrow f = g\)，充分性得证。必要性显然。证毕。

性质 5：积性函数的狄利克雷卷积是积性函数。

证明：考虑积性函数 \(f\) 和 \(g\) 的狄利克雷卷积 \(h\) 。若 \(a\perp b\) ，则
\[\begin{aligned}h(n)h(m) & = \left(\sum\limits_{d_1\mid n} f(d_1) g\left(\dfrac n {d_1} \right)\right)\left(\sum\limits_{d_2\mid m} f(d_2) g\left(\dfrac m {d_2} \right)\right) \\ & = \sum\limits_{d\mid nm} f(d) g\left(\dfrac {nm}{d} \right) \\ & = h(nm)\end{aligned}\]其中 \(d = d_1d_2\) 。第二步依赖于 \(f\) 和 \(g\) 的积性：\(f(d_1) f(d_2) = f(d_1d_2) = f(d)\) 。证毕。

性质 6：积性函数的逆元是积性函数。

证明：设 \(g = f ^ {-1}\) 。根据 \(f\) 的积性可知 \(g(1) = \dfrac 1 {f(1)} = 1\)，所以 \(g(n) = g(1) g(n)\) 。
考虑归纳法。对于 \(n, m > 1\) 且 \(n\perp m\)，假设对于任意 \(xy < nm\) 且 \(x\perp y\) 均有 \(g(xy) = g(x)g(y)\) 。因 \(n = 1\) 或 \(m = 1\) 时命题成立，只需证明 \(g(nm) = g(n)g(m)\) 。
\[\begin{aligned}g(nm) & = -\sum\limits_{d \mid nm, d \neq nm} g(d)f\left(\dfrac {nm} d\right) \\& = -\sum\limits_{a\mid n, b\mid m, ab\neq nm} g(a) g(b) f\left(\dfrac n a\right) g\left(\dfrac m b\right) \\& = f(1) ^ 2g(n)g(m) -\sum\limits_{a\mid n} g(a) f\left(\dfrac n a\right) \sum\limits_{b\mid m}g(b) g\left(\dfrac m b\right) \\& = g(n)g(m) - \epsilon(n) - \epsilon(m)\end{aligned}\]因为 \(n, m > 1\)，所以 \(\epsilon(n) = \epsilon(m) = 0\)，所以 \(g(nm) = g(n)g(m)\) 。证毕。
综合性质 5 和性质 6，两个积性函数的积与商都是积性函数。注意，积性函数的和与差不是积性函数。
3.2 线性筛 Dirichlet 卷积根据积性函数的狄利克雷卷积是积性函数这一结论，我们尝试在线性时间内筛出 \(h = f * g\) 。
写出 \(h\) 的表达式，有
\[h(n) =\begin{cases}1 & n = 1 \\\sum_{c = 0} ^ k f(p ^ c)g(p ^ {k - c}) & n = p ^ k \\h(p ^ k)h(m) & n = p ^ k m(m > 1, p\nmid m)\end{cases}\]对于第一和第三种情况，线性筛时可以总代价 \(\mathcal{O}(n)\) 求出。关键在于 Case 2，若 \(f\) 和 \(g\) 在质数幂处的取值已经求出，则需要 \(\mathcal{O}(k)\) 的时间计算。

特别的，当 \(f\) 为完全积性函数时，\(h(p ^ k)\) 可以写作 \(f(p)h(p ^ {k - 1}) + g(p ^ k)\)，可以 \(\mathcal{O}(1)\) 方便地计算。对于 \(g\) 同理。

尝试估计第二部分的复杂度。考虑到所有小于 \(\leq \sqrt[k]n\) 的质数会对复杂度产生 \(\mathcal{O}(k)\) 的贡献，因此
\[T(n) = \sum\limits_{x = 1} ^ {\log_2 n} x\pi(\sqrt[k]n) = \sum\limits_{x = 1} ^ {\log_2 n} \dfrac {x\sqrt[x] n}{\ln \sqrt[x] n} = \dfrac 1 {\ln n} \sum\limits_{x = 1} ^ {\log_2 n} x ^ 2\sqrt[x] n\]感性理解，\(x ^ 2 \sqrt[x]{n}\) 随着 \(n\) 增大，\(x\) 增大时 \(x ^ 2\) 一项增大的速度远小于 \(\sqrt[x]{n}\) 衰减的速度。从这一点入手，考虑证明 \(x ^ 2 \sqrt[x] n \leq \mathcal{O}(n)\) 。
当 \(x = 1\) 时显然成立，否则考虑 \(x\in [2, \log_2 n]\) 时 \(x ^ 2\) 的最大值 \(\log_2 ^ 2 n\) 与 \(\sqrt[x] n\) 的最大值 \(\sqrt n\) 之积，因为当 \(x\to +\infty\) 时 \(\log_2 x\) 是 \(\sqrt x\) 的高阶无穷小，所以 \(\mathcal{O}(\sqrt n\log ^ 2 n) \leq \mathcal{O}(n)\) 。
因此，\(T(n) \leq \dfrac 1 {\ln n} \sum\limits_{i = 1} ^ {\log_2 n} \mathcal{O}(n) = \mathcal{O}(n)\) 。
综上，使用线性筛求出两个在质数幂处取值已知的积性函数的狄利克雷卷积在 \(1\sim n\) 处的取值的时间复杂度为 \(\mathcal{O}(n)\) 。
我们得到了积性函数可线性筛的更弱的条件：可以 \(\mathcal{O}(k)\) 时间计算质数幂处的取值。
3.3 狄利克雷前缀和前置知识：高维前缀和。
任意数论函数 \(f\) 卷常数函数 \(1\) 等价于对 \(f\) 做狄利克雷前缀和：令 \(g = f * 1\)，则 \(g(n) = \sum\limits_{d\mid n} f(d)\) 。