Min_25筛
枫林晚
·
·
个人记录
%%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)
其实这里意义变了一下，对应：
①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)
劣势：多组数据没有记忆化，就没什么优势了。必须是积性函数。（杜教筛如果能构造卷积，不是积性函数也可以的）
稍微难写一些。