min25筛法，powerful number 筛法

Min25筛法，以及PN筛的不完全理解。

Min25 筛法

个人感觉这种筛法挺暴力的。

我现在还记得lxn跟我说这种筛法最重要的部分是筛素数前缀和。

\(F(n)=\sum_{p\in\mathbb{P},p\leq n}f(p)\)。

这个该怎么做呢？？？容斥就好了，我们第一次把所有的都算进去 \(\sum_{p\leq n}f(p)\)，然后从小往大枚举质数，一个一个筛去。

也就是 \(F(n)\gets F(n)-(F(\lfloor n/p\rfloor)-\sum_{x<p,x\in\mathbb{P}}f(x))f(p)\)。就是这么简单,减去是我们需要保证现在每个数最小质因子就是 \(p\),一定有不符合的素数减去即可。注意我们能这么做的前提是在质数处是完全积性函数。

然后这部分只需要 \(\tilde{O}({n^\frac{3}{4}})\) 即可。

然后对于单点求前缀和；

\(F(n,p)\) 表示最小质因子 \(>p\) 的签注和，那么我们枚举最小质因子 \(p^e\)。此时因为在 \(f(p^e)\) 处积性，所以直接：

\(F(n,p_0)\gets F(\lfloor n/p^e\rfloor,p)f(p^e)\)

另外的我们需要算上 \(p\) 和 \(p^k\) 贡献。

因为 \(p\) 可能有值域个，所以我们需要预处理素数的和，但是 \(p^2\) 只有根号个，我们暴力计算即可。

值得注意的是我们在定义上最好避开 \(x=1\) 这个特殊情况，eg我们定义 g 的初始状态时候要定义的是 \(\sum_{i=2}^nf(i)\)，这样可以有效的避免素数算重。我们只需要在考虑完合数时候直接算出质数即可。

---

PN筛。

想对积性函数 \(f(x)\) 求前缀和。

设 \(g(x)\) 为 \(x\in\mathbb{P}\) 时候的拟合函数，\(g(p)=f(p),p\in\mathbb{P}\)。

所以我们设 \(h=\frac{f}{g}\) 这里是狄利克雷除法。

也就是说 \(h\otimes g=f\)。

考虑 \(f(p)=h(p)g(1)+g(p)h(1)\)，而 \(g(p)=f(p)\)，可得 \(h(p)=0\)，进而得到，\(h(p)\) 的非 powerful number 出取值是0. \[ \begin{aligned} \sum_{i=1}^{n}f(i)=\sum_{i=1}^{n}\sum_{d\mid i}g(d)h(i/d)=\sum_{d=1}^{n}h(d)\sum_{i=1}^{n/d}g(d)\\ \end{aligned} \] 发现 \(h\) 我们只需要考虑 powerful number 处的点值。

接下来就是 \(g\) 的前缀和，所以接下来就仁者见仁义者见义了。

具体配凑可以根据贝尔级数来配凑。

贝尔级数一句话就是如果再每个 \(\bmod p\) 下级数相乘相等，那么整体上迪利克雷卷积就相等。

一个构造拟合函数的 trick是迪利克雷卷积=质数处加法。

\(f=d*d,f(p)=d(p)+d(p)=4\)