未完工，先放上来
筛一个积性函数\(f(n)\)的前缀和\(S(n)=\sum_{i=1}^n f(n)\)，这个函数还需要满足的性质是\(f(p)\)是一个关于\(p\)的多项式、\(f(p^k)\)可以快速计算。
考虑质数单独提出来算，合数在它最小（大？）的质数处统计。
考虑积性函数的性质还不够优秀，不如把多项式的各项拆开来分别算，最后再合在一起。
于是在这一步中假定\(f(p)=p^t\)，它就完全积性了。
记\(P_j\)为从小到大第\(j\)个质数
\[
g(n,j)=\sum_{i=1}^n [i\in Prime\ \ \text{or}\ \ minP(i)> P_j]f(i)
\]
显然，要求所有质数的\(f\)值和，就是\(g(n,|P|)\)。
而\(g\)的初值比较麻烦，但考虑所有不为质数的值最终都会被筛掉，那么一开始可以把所有\(f(i)\)当成质数来算，即\(f(i)=i^t\)。
从小到大枚举\(j?\)来递推\(g(n,j)?\)，有如下转移式：
\[
g(n,j)=\begin{cases}
g(n,j-1)&,P_j>\sqrt{n}\g(n,j-1)-f(P_j)\times(g(\lfloor \frac{n}{P_j}\rfloor,j-1)-\sum_{i=1}^{j-1} f(P_i))&,P_j\le \sqrt{n}
\end{cases}
\]
第一个式子：\(P_j^2>n?\)了，所以不会有多的数被筛掉。
第二个式子：把最小质因子是\(P_j?\)的筛掉。
（注意现在这个函数的性质非常好，所以当成质数来算还是可以有完全积性函数的性质）
于是可以\(O(n\times |P|)?\)搞出\(n?\)个数的\(g(n,|P|)=\sum_{i=1}^n [i\in Prime]f(i)?\)，但这样还是太多了。在第二步中我们会发现其实根本不需要\(O(n)?\)的所有\(g(n,|P|)?\)。
请注意在这一步中\(f(n)\)不再完全积性了。
记
\[
S(n,j)=\sum_{i=1}^n [minP(i)\ge P(j)]f(i)
\]
那么又会有递推式：
\[
S(n,j)=g(n,|P|)-\sum_{i=1}^{j-1} f(P_i)+\sum_{k\ge j,P_k\le Sqr} \sum_{P_k^{e+1}\le n} (f(P_k^e)S(\frac{n}{P_k^e},k+1)+f(P_k^{e+1}))
\]
（这里面\(f(P_k^e)S(\frac{n}{P_k^e},k+1)?\)可以直接乘起来的原因是\(S(n/P_k^e,k+1)?\)中所有元素都与\(P_k?\)互质）
注意\(S(n,j)\)只调用了\(g(n,j)\)和\(S(\frac{n}{P_k^e},k+1)\)，所以第一步中只需要算出所有\(g(n/i,j)\)就够了，而这是\(O(\sqrt{n}\times |P|)\)的。
这东西直接算就好了，不用记忆化。
最后总复杂度可以被证明是\(O(\frac{n^{3/4}}{\log n})\)？反正我不会证明，直接用就好了。
原文：https://www.cnblogs.com/p-b-p-b/p/10807098.html