前置姿势
其实不看也没关系
用途和限制
在\(\mathrm{O}(\frac{n^{0.75}}{\log n})\)的时间内求出一个积性函数的前缀和。
所求的函数\(\mathbf f(x)\)要满足以下条件：
- \(\mathbf f(p)\)是一个多项式，其中\(p\)是质数
- \(\mathbf f(p^c)\)要能够快速计算。
算法流程
首先我们需要求出对于每一个\(\left\lfloor \frac ni\right\rfloor\)求出\(\sum_{i=1}^x [i \in P] \mathbf f(i)\)，其中\(P\)是质数集合。
首先筛出\(\sqrt n\)以内的质数，设\(P_j\)表示从小到大第\(j\)个质数。
设\(\mathbf g(n, j)\)表示所有最小质因子大于\(P_j\)的数加上质数的\(\mathbf f(i)\)的和。
那么\(\mathbf g(n, |P|)\)就是所求。
考虑\(\mathbf g(n, j)\)的转移，分两种情况。
\(P_j^2 > n\)
这个质数不会造成任何影响，于是\(\mathbf g(n, j) = \mathbf g(n, j - 1)\)。
\(P_J^2 \leq n\)
这里我们要考虑筛掉了多少个数字。
那么筛掉的数字中一定含有最小质因子\(P_j\)，所以我们考虑减去\(\mathbf g(\frac n{P_j}, j - 1)\)，但是这样我们多减了前\(j - 1\)个质数的\(\mathbf f\)之和，所以要加上\(\sum_{i=1}^{j - 1}\mathbf f(P_j) = \mathbf g(P_{j - 1}, j - 1)\)
总结一下就是：
\[
\mathbf g(n,j)=
\begin{cases}
\mathbf g(n,j-1)&P_j^2\gt n\\
\mathbf g(n,j-1)-\mathbf f(P_j)[\mathbf g(\frac{n}{P_j},j-1)-\mathbf g(P_{j - 1}, j - 1)]&P_j^2\leq n
\end{cases}
\]
这里可以滚动数组求一下。（感觉和魔力筛很像呢）
到这里我们发现我们已经对于\(x = \left\lfloor \frac ni\right\rfloor\)求出\(\sum_{i=1}^x [i \in P]\mathbf f(i)\)
设\(\mathbf S(n, j) = \sum_{i=1}^n [\mathrm{minp}(i) \geq P_j]\mathbf f(i)\)
那么最终的答案为\(\mathbf S(n, 1) + 1\)
然后我们将\(n\)以内的数字分为质数和合数
质数部分我们得出答案了，为\(\mathbf g(n, |P|) - \mathbf g(P_{j - 1}, j - 1)\)
考虑合数，其实很简单，考虑枚举最小质因子和其出现次数，然后爆算就可以了。
\[
\mathbf S(n,j)=\mathbf g(n, |P|) - \mathbf g(P_{j - 1}, j - 1)+\sum_{k=j}^{P_k^2\le n}\sum_{e=1}^{P_k^{e+1}\le n}\mathbf S(\frac{n}{P_k^e},k+1)\times \mathbf f(P_k^e)+\mathbf f(P_k^{e+1})
\]
然后就没啦。
最后讲一个东西，就是\(\mathbf S\)不用记忆化。
例题什么的以后再补吧。