min_25 筛

oisdoaiu · 2022-06-19 16:47:47 · 个人记录

大概只会用到素数个数

作用

假设有一个积性函数 f(x)，满足 f(p^k) 是关于 p 的多项式。

则 min_25 可以用来求 f 的前缀和。（单点求值）

过程

min_25 主要思想是把质数和合数分开考虑，对于合数考虑枚举最小质因子进行递归处理。

显然 S(n) 可以分为质数的 f 和合数的 f 加起来，分为两个部分处理。

第一部分

令 p_i 表示从小到大第 i 个质数，minp(x) 表示 x 的最小质因子。

由于 f(p) 是一个多项式，我们考虑将每一项拿出来单独处理。（比如说 f(p)=p+p^2，就分别计算 p 和 p^2 的和再加起来）

所以这里考虑一般情况，设 h(x)=x^k，显然 h 是一个完全积性函数。

设一个 dp。

那么 g(n,\infty) 就表示 n 以内所有质数对 f 的贡献。

实际上第二维只需要处理到 \le \sqrt n 的质数，因为如果是合数就至少包含两个质因子，所以小的那个肯定小于根号。

考虑从 g(n,i-1) 推到 g(n,i)，减少的是那些最小质因子为 p_i 的合数，也就是：

但是 minp(x)=p_i 的限制不是很好弄，这里 h 是完全积性函数的好处就体现出来了，h(x)=h(\frac x{p_i})\cdot h(p_i)。

所以我们考虑将 x 除掉一个 p_i，将限制变为 minp(\frac x{p_i})\ge p_i，然后可以直接乘上 h(p_i)。

初始化也就是 g(n,0)，相当于就是 \sum_{i=1}^nh(i)。（可以理解为 p_0=1）

显然会进行 O(\text{多项式次数}) 次第一部分，为了方便后面描述，令 H(n) 表示 n 以内所有质数的 f 的和。

实际上根据过程，我们可以得到所有 H(\lfloor\frac nx\rfloor) 的值。

第二部分

类似于第一部分，设一个dp：

注意区别，第一部分是对 h 求和，这里是对 f 求和，而 f 只是积性函数，并不是完全积性函数，所以不能套用做法

为了方便，我们令 p_0=1，那答案就是 S(n,0)。

考虑如何求 S(n,i)，分为质数和合数两部分，对于合数部分枚举最小质因子以及次数。

后面那个 [k>1] 是因为 f(p^k) 也要做出贡献，而 p^k 除掉 p^k 只有 1 了，但是 S(\lfloor\frac n{p_j}\rfloor,k) 里面没有包含 1，而 >1 是因为 p^1 贡献放在质数里算了。