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

证明：设 \(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)\) 。
对每个 \(n\) 计算给定数论函数在其所有因数处的取值之和有很好的实际含义，因此狄利克雷前缀和是比较重要的算法。
将每个数 \(n\) 写成无穷序列 \(a_n = \{c_1, c_2, \cdots, c_i, \cdots\}\) 表示 \(n = \prod p_i ^ {c_i}\) ，其中 \(p_i\) 表示第 \(i\) 个质数。因为 \(x\mid y\) 的充要条件为 \(a_x(c_i) \leq a_y(c_i)\) ，所以 \(f * 1\) 可以看成对下标做关于其无穷序列的高维前缀和，即 \(g(n) = \sum\limits_{\forall i, a_d(c_i) \leq a_n(c_i)} f(d)\) 。