Tony102's Blog - Min_25筛
type: channel
link: https://tony102.com/index.php/tag/Min_25%E7%AD%9B/
items: Min_25 筛

Min_25 筛
type: item
date: 2021-08-29T08:27:00+08:00
description: 摘要有人也叫做扩展埃氏筛？其实确实挺像的，对于一类积性函数，函数在质数上的取值容易求得，整个函数在任意一点的值、求和、乘积都有办法通过该类方法求得。对于函数有如下要求：积性函数设 $p$ 为质数，那么 $f(p)$ 是一个低阶多项式$f(p^k)$ 的值可以快速求出定义以 Luogu 模板题为例def. 积性函数 $f(x)$ 且满足 $f(p^k) = p^{k}(p^{k} - 1)$，求 $\sum\limits_{i=1}^{n} f(i)$步骤一：按照质数分类整个函数的求和答案可以分为函数在质数上的值的和与合数上的值的和。也就是：（为了方便下面均使用 $P$ 表示质数集，$p$ 表示枚举的质数）$$ \sum\limits_{i=1}^{n} = \sum\limits_{p \in [1,n]} f(p) + \sum\limits_{i=1 \& i \notin P}^{n} f(i) $$这一步还是非常简单步骤二：将合数分解质因数以计算函数值枚举后面合数的最小质因子和次数，注意所有质因子都因 $\leq \sqrt{n}$ 。注意下式中使用 $minp$ 代表最小质因子。$$ \sum\limits_{p \in [1,n]} f(p) + \sum\limits_{p^e \in [1,n] \& p \in [1, \sqrt{n}]} (\sum_\limits{i = 1 \& minp > p}^{\frac{p^e}{n}} f(i)) $$看一下这个看起来非常牛逼的式子。其实也很好理解。前面的项没有变，仍然是函数在质数上的值的和。后面的项首先枚举 $[1,n]$ 中的每一个质因子 $p$ 和它的指数 $e$，并且 $p \leq \sqrt{n}$，后面再单独乘上函数在 $minp > \sqrt{n}$ 处的取值。步骤三：通过第一个 dp 计算后面项的值我们知道函数在质数上的取值是一个低阶的多项式，我们通过一个 dp 来计算。整个 Min_25 筛的过程中运用了两次 dp，这是第一次。这个 dp 确实挺智慧的。设 $g(n,i)$ 满足：（$\lor$ 符号表示逻辑或运算）$$ g(n,i) = \sum\limits_{i=1}^{n} [i\in p \lor minp > p_j] i^k $$因为是一个低阶多项式，所以 $k$ 很小，不会超过二次幂（应该没有恶心题有三次幂吧...）这个 dp 的作用就是求 $[1,n]$ 中所有满足条件：质数或 $minp > p_j$ 的数的 $k$ 次幂和。考虑转移。若 $n < p_{j}^{2}$ ，那么 $g(n,i) = g(n,i - 1)$若 $p_j^{2} \leq n$， 则被筛掉的质数一定有 $p_j$ ，那么要 $-g(\frac{n}{p_j}, j - 1)$注意上面减去的项中，因为 $p_j^2 \leq n \Longleftrightarrow p_j \leq n / p_j$, 所以有 $minp < p_j$ 的 $n’$ 被减去，这部分要加回来：$g(p_{j-1}, j-1)$总的转移式：$$ g(n,j) = g(n,j-1) - p_j^k(g(\frac{n}{p_j}, j-1) - g(p_{j-1},j-1)) $$注意若 $n \in P$ ，就无需减去后面那一坨了，直接 $g(n,j) = g(n,j-1)$性质来了，$g(p_{j-1},j-1)$ 这一项就是前 $j-1$ 个质数的共 $k$ 次幂和。我们设 $sp_n = \sum\limits_{i=1}^{n} p^k$claim: $\lfloor \frac{\lfloor \frac{n}{a} \rfloor} {b} \rfloor = \lfloor \frac{n}{ab} \rfloor$利用整除分块可以计算这一部分的答案。步骤四：求解最终答案现在仅仅需要将上面的计算整合，算出最终答案。再次使用 dp，这个 dp 我们叫第二个 dp。设 $s(n,x)$ 表示求 $[1,n]$ 中所有 $minp > p_x$ 的 $f(x)$ 之和。$$ s(n,x) = g(n,p_x) - sp_x + \sum\limits_{p^e \leq n \& k>x} f(p_k^e) (s(\frac{n}{p^e}, k + [e \neq 1])) $$上式分为两部分，前一部分是计算 $ > p_x$ 的数，后一部分是 $minp > p_x$ 的合数，枚举质因子计算即可。我们可以递归求解 $s$，最后答案在 $s(n,0)$实现我估计自己写还是写不出，还是要看代码。先讲一些要注意的地方。以模板题为例。首先你要预处理处质数…