正文
关于 min_25 筛的入门以及复杂度证明
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
min_25 筛是由 min_25 大佬使用后普遍推广的一种新型算法，这个算法能在 \(O({n^{3\over 4}\over log~ n})\) 的复杂度内解决所有的积性函数前缀和求解问题（个人感觉套上素数定理证明的复杂度的话应该要把下面的 log 改成 ln ，不过也差不多啦~）
其实 min_25 筛的入门TXC 大佬的 blog 已经写的非常棒了QVQ
所以搬博客的话鉴于博主太懒了就不干了...直接帮 TXC 大佬安利博客完事
这篇博客主要的目的是证明网上大多没有的 min_25 筛的复杂度
所以你首先得学会 min_25 筛...
前置芝士
Min_25 筛
素数定理
proof
Min_25 筛
素数定理
首先我们知道 min_25 筛做了两件事：
-
筛出一个所求函数的质数前缀和
-
递归/循环 得到所求函数的前缀和
对于第一个部分和第二个部分我们发现都有一个枚举质数的过程，那么我们需要先知道 n 范围内的质数个数
这就需要素数定理了，素数定理指：在 n 以内的素数个数是 \(O({n\over ln~ n})\) 的（下面为了方便起见就用 \(log ~n\) 代替这里的 \(ln~n\) 了 ）
至于具体证明就不是本博客的任务了 QVQ
我们可以根据这一点结合埃氏筛法的复杂度得知：
我们在进行 min_25 中处理的 \(2\sqrt n\) 个数的函数前缀和时，一个数 x 被筛到过 \(O({\sqrt x\over log~ \sqrt x})\) 次
并且，无论是筛出所求函数关于 x 的质数前缀和还是全部的前缀和，都是这个次数（如果你写过循环代替递归版的 min_25 的话，就更加清楚这是为什么了）
这里可以贴出我写的一种 min_25 筛的版本（以筛 mu 的前缀和为例）：
inline int ID(Rg int x){
return x<=sq?id1[x]:id2[n/x];
}
inline int calc(Rg int k,int j){
return w[k]>=p[j]?h[k]-j+1:0;
}
inline void Min_25(ll n){
sq=sqrt(n),m=0; int tot=0;
for(tot=1;1ll*p[tot]*p[tot]<=n;++tot);
for(Rg ll l=1;l<=n;l=w[m]+1){
w[++m]=n/(n/l),
h[m]=w[m]-1,Mu[m]=0,
//这里的 h 指质数个数的前缀和 , Mu 指莫比乌斯函数的前缀和
if(w[m]<=sq) id1[w[m]]=m;
else id2[w[m]]=m;
}
for(Rg int j=1;j<=tot;++j){
for(Rg int i=m;i&&1ll*p[j]*p[j]<=w[i];--i)
h[i]-=h[ID(w[i]/p[j])]-j+1;
}
for(Rg int j=tot;j;--j){
for(Rg int i=m,k;i&&1ll*p[j]*p[j]<=w[i];--i)
Mu[i]-=Mu[k]-calc(k,j+1);
}
for(Rg int i=m;i;--i) Mu[i]-=h[i];
}
不压行真的好难受嘤嘤嘤...
我们发现上面筛出 mu 前缀和的时候两个处理部分都是用了极其类似的双重循环，（并且保证了答案是对的...），那么也就可以证明上面的说法了
所以我们就可以列出复杂度的式子：
\[O(Min\_25)=\sum_{x=1} ^{\sqrt n} O({\sqrt x\over log~ \sqrt x}) + \sum_{x=1} ^{\sqrt n} O({\sqrt {n\over x}\over log~ \sqrt {n\over x}})
\]
\]
主定理一波就是：
\[\sum_{x=1} ^{\sqrt n} O({\sqrt {n\over x}\over log~ \sqrt {n\over x}})
\]
\]
然后开始积分：
\[O\Big( \int_1^{\sqrt n} {\sqrt {n\over x}dx\over log~ \sqrt {n\over x}} \Big)
\]
\]
然后正常做法就难搞了，那么我们假一点，反正求的是大致复杂度，那么我们让下面的表达式直接变为 \(log~ n\)（这里把常数直接略去） 这样我们的任务就只剩下求上面表达式的积分了
至于这样为什么可行？ 我们发现下面的表达式中有一个 log ，虽然我们让下面的表达式都变大了，但在 log 后，不过是少个常数的问题
如果这里有疑问的话，我们也可以把下面的表达式改成最小的 \(log~\sqrt{n}={1\over2}log~\sqrt{n}\)，然后我们再把 \(1\over 2\) 忽略，这样的结果和上面是一样的...
于是乎原来的式子就变成了：
\[O\Big( {\int_1^{\sqrt n} \sqrt {n\over x}dx\over log~ n} \Big)
\]
\]
\[O\Big( {\sqrt n \int_1^{\sqrt n} x^{-{1\over2}} dx\over\ log~ n} \Big)
\]
\]
上面的那个积分已经是个多项式了：
\[O\Big( {\sqrt n ·( 2{\sqrt n}^{1\over2} )\over\ log~ n} \Big)
\]
\]
\[O\Big( { n^{1\over 2} · n^{1\over 4} \over\ log~ n} \Big)
\]
\]
\[O\Big( {n^{3\over 4} \over\ log~ n} \Big)
\]
\]
这样整个 min_25 筛的复杂度就证明完毕啦~
