Min_25筛
枫林晚
2021-11-20 20:14:31
%%yyb
%%zsy
一、
基本操作：
筛1~N中的素数个数。n=1e9
设F(M,j)表示，2~M的所有数中，满足以下条件之一的数的个数：
①x是质数
②x最小质因子大于（注意是大于没有等号）$P_j$（第j个质数）
转移方程：
$F(M,j)=F(M,j-1)-(F([M/{P_j}],j-1)-(j-1))$
理解的话，考虑埃氏筛的做法（这里从${P_j}^2$开始筛）
统计这一次被删掉的数的个数也即形如：$x=P_j*some P_{j+x} (x>=0 \&\&some P_{j+x}<=[M/P_j])$
其实就是M以内，最小质因子为$P_j$的数的个数（除了$P_j$自己）
可以发现，每一个这样的$someP_{j+x}$都在后面枚举到并且减去了
由于是从$P_j^2$开始筛，所以类似$P_j*P_{j-1}$的之前已经被减掉了，不包含在$F(M,j-1)$里。
所以再加上$(j-1)$
具体方法的话：
其实最后一个j，满足$P_j^2<=N\&\&P_{j+1}^2>N$
先要找到这个j，也就是筛出来小于$[\sqrt N]$的所有质数
以大于根号n下取整的质数作为最小质因子的数，要不然本身就是质数，要不然一定就大于N了。
设这个j为cnt
由于最终的答案是：$F(N,cnt)$
所以涉及一切所谓$M/P_j$的，其实都是一些$N/x(2<=x<=N)$只有根号种
把所有这根号n个数都先找出来，放在第一维的位置，设上界为lim，val[lim]=N
cnt作为第二维j的上限
然后外层枚举j，内层枚举i
这样用数组$f[M]$一维直接代表$f[M][j]$（类似0/1背包那种）
大概代码长这样：
for(j=1->cnt)
for(i=lim->0){
f[i]=f[i]-(f[i/p[j]]-(j-1))
}
一个剪枝是，如果
存在$P_j^2>M$那么其实$F[M][j]=F[M][j-1]$（你用$P_j$不会多干掉任何一个数）
由于是一维数组，所以不用管相当于直接继承。
所以可以加这个剪枝：
for(j=1->cnt)
for(i=lim->0){
if(i/p[j]<p[j]) break; //后面i更小，一定都不行了
f[i]=f[i]-(f[i/p[j]]-(j-1));
}
传说复杂度$O(N^{\frac{3}{4}})$
二、
一个进阶的计算需求是：
求$\sum_{i=1}^n i^k*[i\space is\space prime]$
其实刚才求的是k=0的特殊情况
公式：$F(M,j)=F(M,j-1)-P_j^k(F([M/{P_j}],j-1)-\sum_{i=1}^{j-1}P_i^k)$
其实这里意义变了一下，对应：
$F(M,j)$表示，1到M中的满足以下条件的所有数的k次方和：
①x是质数
②x最小质因子大于（注意是大于没有等号）$P_j$（第j个质数）
就是多了一个权值
后面的$\sum_{i=1}^{j-1}P_i^k$可以预处理
三、
Min_25筛能干的是当然不止这个
实际上爆踩杜教筛，可以筛符合以下条件的一切积性函数：
①f(p)=关于p的低次多项式
②f(p^c)可以快速算出
例如：求：
$\sum_{i=1}^N \phi (i)$
类比，设：$G(M,j)$表示2~M满足x的最小质因子>=$P_j$的数的$phi(x)$的和。
考虑枚举最小质因子$P_t$以及它的次数e那么有：
$G(M,j)=\sum_{t=j}^{cnt} \sum_{e=1}^{p_t^{e+1}<=M} [\phi(p_t^e)*G([M/(p_t^e)],t+1)+\phi(p_t^{(e+1)})]$
$+(F(M)-(F(p_{j-1})))$
第一部分枚举每个除了质数自己的最小质因子>=$P_j$的数。能乘G的原因是积性函数
第二部分枚举每个质数的$\phi$之和。
（这里F(M)表示，小于等于M的质数的phi之和。可以用$\sum_{i=1}^n i^1*[i\space is\space prime]-\sum_{i=1}^n i^0*[i\space is\space prime]$
也就是$\phi(p)=p-1$
答案是$G(N,1)+F(1)$
具体实现。。。。见下面例题
对于一般的函数，把所有的$\phi$换成$F$即可。当然F要满足开头的两个性质
然后大功告成！！！
例题：简单的函数——Min_25筛
DIVCNT2&&3 - Counting Divisors
对比杜教筛
优势：理论计算快，实际计算效果很好，n<=1e9时候优势很大
几乎适用各种积性函数。不需要构造卷积形式
空间优秀！O(n^0.5)
劣势：多组数据没有记忆化，就没什么优势了。必须是积性函数。（杜教筛如果能构造卷积，不是积性函数也可以的）
稍微难写一些。