解决积性函数 \(f\) 的前缀和问题。
下文中的一些记号：
-
\(F(n) = \sum_{i = 1}^{n} f(i)\)：\(f(i)\) 的前缀和。
-
\(\text{lp}(n)\)：\(n\) 的最小质因子。
-
\(p_k\)：全体质数中第 \(k\) 小的质数。
-
\(\dfrac{x}{y}\)：默认下取整。
首先尝试解决这个问题：求出
\[G(m) = \sum_{i \in P, i \le m} f(i) \]其中 \(m \in \{\dfrac{n}{1}, \dfrac{n}{2}, \dfrac{n}{3} \cdots , \dfrac{n}{n}\}\)，一共有 \(\sqrt n\) 中取值。
考虑 dp。设 \(g(j, m)\) 表示：
\[\begin{aligned} g(j, m) &= \sum_{1 \le i \le m} [i \in P \bigcup \text{lp}(i) > p_j] f'(i) \end{aligned} \]也就是对于所有的质数或者最小质因数大于 \(p_j\) 的 \(f'\) 求和。
这里的 \(f'\) 需要满足下面的三个性质：
-
\(\forall p \in P, f'(p) = f(p)\)。
-
\(f'\) 是完全积性函数。
-
\(\sum f'\) 可以快速求值。
初始时，\(g(0, m) = \sum_{2 \le i \le m} f'(i)\)。
转移时分两种情况：
-
若 \(p_j ^ 2 > m\)：\(g(j, m) = g(j - 1, m)\)。因为不存在 \(i \in [1, m]\)，使得 \(\text{lp}(i) > p_j\)。
-
若 \(p_j ^ 2 \le m\)：
这个式子怎么理解呢？首先，这里可以理解成从 \(g(j - 1, m)\) 里面筛掉所有 \(\text{lp} = p_j\) 的 \(f'\) 值。而筛掉的值一定可以表示成 \(p_j \times q\)，其中 \(q\) 是一个 \(\le \dfrac{m}{p_j}\) 而且最小质因子 \(\le p_j\) 的数。最后减掉的那块，是 \(g(j - 1, \dfrac{m}{p_j})\) 里面的那部分质数。由于 \(f'\) 是完全积性函数，这两部分可以直接相乘。
以上部分时间复杂度被证明是 \(O(\dfrac{n ^ {0.75}}{\log n})\)。
上面求出了 \(G(m) = \sum_{i \in P, i \le m} f(i) = g(\pi(m), m)\)。
标签：le,dfrac,min25,笔记,text,lp,sum,质数 From： https://www.cnblogs.com/Link-Cut-Y/p/18575211