min25筛入门

考虑到\(min 25\)筛的神通广大和博主记性之差,博主决定写一个小结,防止遗忘

part 1

给定积性函数\(f(x)\),求\(\sum \limits ^n _{x=1} f(x)[x \in Prime]\)
注:下文会用\(p_i\)表示第\(i\)个质数,\(Prime\)表示质数构成的集合,\(R(x)\)表示\(x\)的最小质因子

我们定义二元函数\(g(i,j)=\sum \limits _{x=1}^if(x)[x \in Prime \ or \ R(x) > Pj ]\)
显然\(\sum \limits ^n _{x=1} f(x)[x \in Prime]=g(n,m),p_m^2\geq n\)
我们考虑二元函数\(g\)的递推方法
我们有
\(g(i,j)=g(i,j-1)-f(p_j)[g(\frac{i}{p_j},j-1)-\sum\limits_{k=1}^{j-1}f(p_k)]\),条件是\(p_j^2 \leq i\)
显然如果\(p_j^2>i\)什么也筛不到,因为不存在有两个大于等于\(p_j\)的质因子的数,那么\(g(i,j)=g(i,j-1)\)
我们主要讲解一下第一个式子
\(g(i,j)\)比\(g(i,j-1)\)多的是以\(p_j\)为最小质因子的合数的\(f(x)\)之和,我们就把这部分减掉,就是\(f(p_j)[g(\frac{i}{p_j},j-1)-\sum\limits_{k=1}^{j-1}f(p_k)]\),
\(g(\frac{i}{p_j},j-1)\)帮我们去除了最小质因子比\(p_j\)小的数,减掉质数的和是因为\(g\)会统计素数
我们发现我们需要调用的\(g\)都是\(g(\lfloor \frac{n}{d} \rfloor,i)\)的形式,所以我们的第一维只有\(O(\sqrt{n})\)种取值
我们省略第二维,空间复杂度\(O(\sqrt{n})\),时间复杂度\(O(\frac{n^{\frac{3}{4}}}{log_2n})\)
举个例子:求\(n\)以内质数的个数

part 2

只能求质数的值未免太差了一点
我们定义一个新的二元函数\(s(i,j)\),
\(s(i,j)=\sum \limits _{x=2}^n f(x),R(A)\geq p_j\)
我们要求一个积性函数的前缀和,答案就是\(s(n,1)+f(1)\)
考虑怎么求得\(s(i,j)\)
质数部分显然是\(g(i,m)-\sum \limits _{i=1}^{j-1}f(p_i)\),考虑合数部分的求法
我们枚举以下的最小质因子及其幂次,可以得到
\(s(i,j)=g(i,m)-\sum \limits _{i=1}^{j-1}f(p_i)+\sum \limits _{k=j}^{p_k^2 \leq i}\sum\limits_{e=1}^{p_k^{e+1}\leq i}s(\frac{i}{p_k^e},k+1)f(p_k^e)+f(p_k^{e+1})\)
这么做不需要记忆化,时间复杂度仍为\(O(\frac{n^\frac{3}{4}}{log_2n})\)
loj 简单的函数

bzoj 4805 欧拉函数求和 460ms

更新一个非递归版本的,运行起来比递归版本慢一些,但是在特判某某倍数方面很有优势

发表评论

电子邮件地址不会被公开。 必填项已用*标注