某积性函数前缀和算法的复杂度分析
\(\newcommand{\lpf}{\textnormal{lpf}} \newcommand{\eps}{\varepsilon}\) 之前做 PE 的时候看到一个很有用的数论技巧：令 \(\lpf(x)\) 表示 \(x\) 的最大质因数，我们考虑把 \([n]\) 分成按照 \(\frac{x}{\lpf(x)}\) 来分类，即 \(S_k = \{x: x / \lpf(x) = k\}\)，然后每一个 \(S_t\) 单独处理。举个例子，假设我们要求一个积性函数 \(f\) 的前缀和 \(F(x) := \sum\limits_{n=1}^x f(n)\)，那么对于一个 \(S_k\)，它里面的数的函数和为： \[ \sum_{n \leq x: n / \lpf(n) = k} f(n) = f(k \lpf(k)) + \sum_{\lpf(k) < p \leq x / k} f(kp) = f(k \lpf(k)) + f(k) \sum_{\lpf(k) < p \leq x / k} f(p). \] 后者只要知道形如 \(\tilde F(x) := \sum\limits_{p \leq x} f(p)\) 这样的和就可以了，而这个是有经典解法的。这个算法的更详细的介绍请参考 The prefix-sum of multiplicative function: the black algorithm 和 关于一种积性函数前缀和的通用筛法的时间复杂度证明 - 知乎。
显然，这个算法的整体复杂度取决于 \(\tilde F\) 的计算复杂度和有多少个不同的 \(k\)。由于每个问题的 \(f\) 性质不同，\(\tilde F\) 的复杂度会有不同，但是后者相对独立。这里我们就开始研究有多少个不同的 \(k\)，即 \(Q_x := \#\{n / \lpf(n): n \leq x\} = \#\{k: k \lpf(k) \leq x\}\) 的大小。