zhongzihao/min_25_sieve

Min_25筛学习笔记

以下参考了这篇博客。

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

设 \(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})\)，但是实际速度比前一部分快很多。