前置知识
线性筛
详见线性筛
数论函数&狄利克雷卷积
欧拉函数
详见欧拉函数
莫比乌斯函数
详见莫比乌斯函数
杜教筛
杜教筛的作用
首先我们要知道,杜教筛是拿来干什么的,其实并没有很高深,就是可以在低于线性时间的复杂度求出积性函数的前缀和。
常见的有很多,比如最常见最简单的是求 \(\mu\) ,\(\varphi...\) 等等。
杜教筛的原理
设我们现在要求积性函数 \(f\) 的前缀和 \(\large S(n)=\sum\limits_{i=1}^nf(i)\)
那么我们再找到任意一个积性函数 \(g\) ,考虑 \(f*g\) 的前缀和:
接下来我们发现这样一件事情:\(\large g(1)S(n)=S(n)\) !
这正是我们要求的东西,于是我们考虑通过算两次来得到 \(\large g(1)S(n)\) :
这时我们把前面的柿子代回去就变成了:
那这有什么用呢?
我们发现,如果我们可以找到一个性质很好的 \(g\) ,使得 \(f*g\) 很好算,那么我们后面的部分就是一个递归+数论分块(这部分复杂度待会分析)
如果直接做,根据主定理分析可以得出时间复杂度是 \(O(n^{\frac 34})\) 的:
进一步优化,我们考虑线性筛预处理出前 \(m\) 个答案,然后我们再杜教筛,这样的复杂度用主定理分析是:
\(m\) 取到 \(\large m=n^{\frac 23}\) 时复杂度最优到:\(\large O(n^{\frac 23})\) 。
杜教筛的实现
代码长这个样子:
inline ll Getpref(int x){
if(x<=t) return pref[x];//线性筛预处理 n^{2/3} 部分
if(preuu[x]) return preff[x]; //unorderedmap的记忆化数组
ll res=GetMulgf(x); //f*g的部分
for(int l=2,r;l<=x;l=r+1){//数论分块的部分
r=x/(x/l);//数论分块
res-=1ll*(GetSum(r)-GetSum(l-1))*Getpref(x/l); //计算后面部分
}
return preff[x]=res;//记忆化
}
杜教筛的应用条件
首先我们需要可以快速求出前 \(\large n^{\frac 23}\) 项的前缀和。
其次需要我们可以找到一个性质很好的 \(g\) 满足:
\(1.\) \(f*g\) 的前缀和可以快速计算。
\(2.\) \(g\) 的前缀和可以快速计算。
(扩展:\(Min25\)筛似乎就没有这么苛刻的条件,并且效率也不错)
练手题目
题面
在低于线性时间内求出:
杜教筛求欧拉函数前缀和
考虑到有 \(\varphi*I=id\) ,于是设 \(g=I\) ,发现剩下的都非常好求:
\(id\) 的前缀和就是等差数列求和,\(I\) 的前缀和就是区间长度。
代码:
inline ll Getprephi(int x){
if(x<=t) return prep[x];
if(prepp[x]) return prepp[x];
ll res=1ll*x*(x+1)/2;
for(ll l=2,r;l<=x;l=r+1){
r=x/(x/l);
res-=1ll*(r-l+1)*Getprephi(x/l);
}
return prepp[x]=res;
}
杜教筛求莫比乌斯函数前缀和
考虑到有 \(\mu*I=\varepsilon\) ,于是设 \(g=I\) ,剩下的也都很好求:
\(\varepsilon\) 前缀和就是 \(1\) ,\(I\) 前缀和同上。
代码:
inline ll Getpremu(int x){
if(x<=t) return preu[x];
if(preuu[x]) return preuu[x];
ll res=1;
for(ll l=2,r;l<=x;l=r+1){
r=x/(x/l);
res-=1ll*(r-l+1)*Getpremu(x/l);
}
return preuu[x]=res;
}
总结
杜教筛就讲到这里了,如果想知道更多扩展可以见 莫比乌斯函数&欧拉函数&筛法 综合运用
这篇文章大部分其实都参考自浅谈杜教筛,这里贴个链接。