面向 J 组的 Min_25 筛 & 复杂度中求和与积分的转换

Revitalize · 2025-05-14 21:50:15 · 算法·理论

0. 前言

OI-wiki 感觉说的并不通俗易懂啊……
写一篇面向普及组选手的 Min_25 筛吧！
（不懂或有误可以指出并私信，必关）

在学之前，先膜拜 Min_25 大佬！！！

1. 问题

首先抛出一个问题：给你一个积性函数 f，让你求 \displaystyle\sum_{i=1}^nf(i) ，也就是 f(i) 的前缀和，怎么做？
杜教筛通过构造一个 g 函数然后用卷积式子解决。
复杂度是 O(n^{\frac{2}{3}}) 。
而如果 f(p) （p 为质数）能快速计算并表达成若干个完全积性函数的和（通常为关于 p 的多项式），且 f(p^c) 也可以快速计算时，就可以使用 Min_25 筛。
完全积性函数的定义是，

注意，a,b 不需要互质！

2. 辅助函数

我们先定义，G(k,n) 为:
从 \color{red}2 到 n 遍历整数 i，对于所有满足以下条件的 i, 对 f(i) 求和。
条件：i 的最小质因子大于等于第 k 个质数。
用数学语言表述，就是：

其中 L(i) 就是 i 的最小质因子，P_k 就是第 k 个质数。
用代码表述，就是：

int ans=0;
for(int i=2;i<=n;i++){
        if(L[i]>=pri[k]) ans+=f(i);
}
return ans;

边界就是当 P_k>n 时 G(k,n)=0。

3. 转化

求这个奇怪的东西有什么用？
先不管，看看怎么求。
首先，我们发现，只有 L(i)\ge P_k 时，f(i) 才对 G(k,n) 产生贡献，所以我们枚举大于等于 P_k 的所有质数作为 i 的最小质因子。
具体怎么枚举呢？
对于每一个 P_j，考虑 L(i)=P_j，那么就有两种情况：

2. ### 第一种情况 对于所有满足第一种情况的 $i$，它们的总贡献就是 $$f(P_j)+\sum_{t=2}^{\lfloor\frac{n}{P_j}\rfloor}f(tP_j)[L(t)\ge P_{j+1}]$$ 为啥得到这个式子呢？ 首先因为 $i$ 是 $j$ 的倍数，所以我们按照学莫反时推式子的原理，转而去枚举 $t=\dfrac {i}{P_j}$。 然后因为 $j$ 是 $i$ 的最小质因子，所以 $t$ 的最小素因子一定大于 $P_j$，或 $t=1$。 所以这个式子的前半部分处理的是 $t=1$ 的情况，就是 $f(P_j)$。（此时 $i=P_j$） $t\ne 1$ 时，前面说过 $t$ 的最小素因子一定大于 $P_j$，即大于等于 $P_{j+1}$。 所以 $L(t)\ge P_{j+1}$ 时，$f(i)$，也就是 $f(tP_j)$ ，才对答案构成贡献。 又因为 $P_j$ 在 $i$ 中的次数等于 $1$，所以 $\gcd(t,P_j)=1$，又因为 $f$ 积性，所以 $f(tP_j)=f(t)f(P_j)$。 所以原式变为： $$f(P_j)+f(P_j)\sum_{t=2}^{\lfloor\frac{n}{P_j}\rfloor}f(t)[L(t)\ge P_{j+1}]$$ 根据 $G$ 的定义，就可以写成： $$ f(P_j)+f(P_j)G(j+1,\lfloor\frac{n}{P_j}\rfloor) $$

注意！下面是关键点！
对于前面的一项 f(P_j),P_j\le n 即可，但对于后面一项 f(P_j)G(j+1,\lfloor\frac{n}{P_j}\rfloor),，必须 P_j^2\le n，即 t\ge P_j，也就是说，当 P_j^2>n 时，后面那一项就是无用的。
因为后面那一项我们要求 t\ne 1，又 j 为 i 的最小素因子，所以必有 t\ge P_j 。

第二种情况

对于所有满足第一种情况的 i，它们的总贡献就是

我们枚举 c 作为 P_j 在 i 中的出现次数。
其余和第一种情况类似，也是枚举 t=\dfrac{i}{P_j^c}。
然后因为 j 是 i 的最小质因子，所以 t 的最小素因子一定大于 P_j，或 t=1。
所以这个式子的前半部分处理的是 t=1 的情况，就是 f(P_j^c)。（此时 i=P_j^c）

现在考虑怎么求 S 。
我们知道 Min_25 筛处理的 f 一般满足这样的性质：
对于质数 p，有 f(p) 是 p 的一个低次多项式。
设该多项式为 ：