===== Min_25筛学习笔记 =====

以下参考了[[http://www.cnblogs.com/zzqsblog/p/8302815.html|这篇博客]]。

大概就是洲阁筛的好写版本。复杂度并没有降低。

设 $f(x)$ 是一个积性函数，且 $f(p)$ 是一个关于 $p$ 的多项式。要求 $\sum_{i=1}^{n}f(i)$。

定义 $g_{k}(x)=\sum_{i=1,i\text{ is prime}\lor\min_{i}> p_{k}}^{x}f(i)$。那么所有质数的 $f(p)$ 之和就是 $g_{m}(n)$，其中 $m$ 是不大于 $\sqrt{n}$ 的最大质数的编号。$g_{0}(x)$ 可以通过自然数等幂和求得。转移类似于背包： $$
\begin{cases}
&g_{k-1}(x)-f(p_{k})(g_{k-1}(\frac{x}{p_{k}})-g_{k-1}(p_{k}-1))&(x\ge p_{k}^{2})\\
&g_{k-1}(x)&(x<p_{k}^{2})
\end{cases}
$$ 这部分的复杂度积一下就是 $\displaystyle{\mathcal{O}(\frac{n^{\frac{3}{4}}}{\log n}})$。

定义 $h_{k}(x)=\sum_{i=2,\min_{i}>p_{k}}^{x}f(i)$。那么答案即为 $h_{0}(n)+f(1)$。转移时直接暴搜，且不要记忆化： $$
h_{k}(x)=g_{m}(x)-\sum_{i=1}^{k-1}f(p_{i})+\sum_{i=k}^{p_{i}^{2}\le x}\sum_{j=1}^{p_{i}^{j+1}\le x}(f(p_{i}^{j})h_{k+1}(\frac{x}{p_{i}^{j}})+f(p_{i}^{j+1}))
$$ 这部分的复杂度为 $\mathcal{O}(n^{1-\omega})$，但是实际速度比前一部分快很多。