杜教筛
（彷佛有不少人在催个人杜教筛呢......）html
前言
- 话说，我是否是在本身的莫比乌斯反演中挖了许多杜教筛的坑啊......
- 本文完整的总结介绍杜教筛，也算是将莫比乌斯反演中的坑所有填满吧！
- 真诚地但愿来阅读这篇学习笔记的每个人，仔仔细细的看完每一段。
- 我相信，只要认真的看完整篇文章并跟着一块儿思考的读者，必定可以有所收获！
- 若是您以前不会杜教筛，那么我但愿这篇文章可以做为您学习杜教筛路上的有力援助，帮助您真正的了解与掌握杜教筛！
- 若是您以前早已熟知杜教筛或只有些模糊的印象，相信您必定也能有所收获！
- (PS：本文较长，请耐心阅读 ovo)
在OI中的意义
- 其实，对于通常的数论题，线性筛已经很是的优秀了。
- 可是就是有那些\(duliu\)出题人，硬是要把数据出到\(1e10\)之类的，就看你会不会杜教筛，min_25筛，洲阁筛等各类神奇的筛法。
(PS:后面这两个筛法我是真的不会了QAQ)
- 要是不会，那就要少十分左右！
- 因此，专门用杜教筛来推式子的题目不多，通常都是用杜教筛优化线性筛，弄到最后的那些分。
- 不过，杜教筛的思想对于推式子是颇有帮助的。（它那种递归求解的形式，以及复杂度\(O(n^\frac{2}{3})\) ）
- 所以，学会杜教筛也是一件挺好的事情！
前置技能
各类函数
概念
- 首先，咱们须要知道有一个东西叫作数论函数
- 数论函数有不少种，可是咱们身为Oier，并不须要知道它的具体的定义，具体的分类。
- 咱们只须要知道，咱们在OI中的数论中所用到的各类函数\(\mu,\varphi\)等都是数论函数。(后面会将常见的都列举出来，固然不仅这两种)。
- 当你了解数论函数后，你就须要知道有一类函数叫作积性函数。
- 仍是一样的话语，咱们日常所惯用的数论函数都是积性函数！
- 不过，对于积性函数的定义仍是有必要了解一下。(毕竟有些函数看上去不常见，其实可能就是积性函数！)
- 积性函数定义：若是已知一个函数为数论函数，且\(f(1)=1\)，而且知足如下条件，若对于任意的两个互质的正整数\(p,q\)都知足\(f(p\cdot q)=f(p)\cdot f(q)\)，那么则称这个函数为积性函数。
- 特殊的，若是当对于任意的正整数\(p,q\)(即不必定互质)，也知足以上这个式子，则称这个函数为彻底积性函数。
- 而咱们的杜教筛，则是用来筛积性函数前缀和的神奇筛法！！！
- 说了这么多概念性的东西，不如来点实质性的！
常见积性函数
- \(\mu(n)\)——莫比乌斯函数。关于这个函数，我在莫比乌斯反演中说的挺清楚的了(233)，(PS：不过我将会在下文中，从另外一种角度介绍它的性质。也算是把坑给填完吧)
- \(\varphi(n)\)——欧拉函数。表示不大于\(n\)且与\(n\)互质的正整数个数，十分常见的数论函数。用数学式子表示即：\(\varphi(n)=\sum_{i=1}^{n}[(n,i)=1]\) (PS:\((n,i)\)表示\(gcd(n,i)\))
- \(d(n)\)——约数个数。表示\(n\)的约数的个数。用式子表示为：\(d(n)=\sum_{d|n}1\)，也能够写做：\(d(n)=\sum_{d=1}^{n}[d|n]\) （其实没什么太大区别啦！）
- \(\sigma(n)\)——约数和函数。 即\(n\)的各个约数之和。表示为：\(\sigma(n)=\sum_{d|n}d=\sum_{d=1}^{n}[d|n]\cdot d\)
(PS：接下来列举的是彻底积性函数)
(PS：表明字母可能会与他人的略有不一样，彷佛在数学中没有统一的字母)c++
- \(\epsilon(n)\)——元函数。彷佛也有人把它叫做\(e(n)\)？其实无所谓啦~~咱们只须要知道\(\epsilon(n)=[n=1]\)。(看到这个是否是有种莫名的熟悉感呢？到了下文中，就会发现这种熟悉感是从哪来的啦！)
- \(I(n)\)——恒等函数。所谓恒等就是这个函数的值恒为\(1\)。
- \(id(n)\)——单位函数。\(id(n)=n\)。
(当第一次看到这些彻底积性函数的时候，是否是有人感受这些彻底积性函数毫无用处，都是一些简单的式子，只不过用符号表示了呢？在下一个前置技能——狄利克雷卷积中，你应该就会改变本身\(naive\)的想法啦~)git
狄利克雷卷积 (\(*\))
基本知识
- 听名字，彷佛是一个很高深的东西。
- 其实，如果不理睬这个名字，只是把它看成一个新定义的符号，你应该就会发现，狄利克雷卷积也不是那样的难理解。
- 定义：两个数论函数\(f\)和\(g\)的卷积为\((f*g)(n)=\sum_{d|n}f(d) \cdot g(\frac{n}{d})\)。前面的括号表明将\(f\)卷\(g\)，后面的括号表明范围。(PS：后面的括号通常能够省略不写，默认为\(n\))
- 很显然，狄利克雷卷积知足如下运算规律：
- 交换律(\(f*g=g*f\))；
- 结合律(\((f*g)*h=f*(g*h)\))；
- 分配律(\((f+g)*h=f*h+g*h\))；
- 在记忆方面，能够类比为乘法的运算法则，其实上面这几条运算规律是能够证实的！
- 举个例子，交换律。咱们看狄利克雷卷积的式子，实质上就是\(n\)的每个约数带入\(f\)中的值，乘上与之对应的约数在\(g\)中的值。
- 显然，当交换\(f\)和\(g\)时，仅仅时枚举约数的顺序发生了改变，而每个约数对答案的贡献是不会有改变的。所以存在交换律！
- 在大体了解了狄利克雷卷积的运算法则后，咱们就须要提到上面所说的积性函数啦！
- 首先，元函数 \(\epsilon\)。所谓元函数，指的就是在狄利克雷卷积中充当单位元的做用，单位元即知足：\(f*\epsilon=f\)。不要小看这个元函数，当元函数配合上结合律时就能够用来证实一些结论啦~
- 除了元函数以外，咱们最为常见的则是\(\mu,\varphi\)之类的的函数，所以咱们须要十分熟练它们与一些常见的彻底积性函数的卷积，以及性质。
(PS：特别要记住一点：积性函数有一个特别重要的性质，那就是（积性函数\(*\)积性函数）仍然为积性函数！！！这个性质能够用来判断可否被杜教筛！)算法
莫比乌斯函数\(\mu\)
- \(\mu\)。在莫比乌斯反演中，咱们曾了解过一个与\(\mu\)有关的性质：\(\sum_{d|n}\mu(d)=[n=1]\)
- 咱们将这个性质表示成狄利克雷卷积的形式即：\(\mu*I=\epsilon\)。这在狄利克雷卷积中是一个很经常使用的恒等式。固然，有了它，咱们也可以证实出莫比乌斯反演啦！
- 开始填坑，证实莫比乌斯反演：
已知：
\[F(n)=\sum_{d|n}f(d)\]
用狄利克雷卷积的形式表示这个式子即：\(F=f*I\)
利用狄利克雷卷积将\(F\)卷上\(\mu\)，获得：
\[F*\mu=f*I*\mu\]
因为狄利克雷卷积具备结合律与交换律，所以原式可化为：
\[\to f*(I*\mu)=f*\epsilon=f\]
即：\(f=F*\mu\)。代入后便可证实莫比乌斯反演：\(f(n)=\sum_{d|n}\mu(d)\cdot F(\frac{n}{d})\)
同理，天然也能够获得莫比乌斯反演的另外一种形式：\(f(n)=\sum_{n|d}\mu(\frac{d}{n})\cdot F(d)\)
(总算填完一个大坑......)
欧拉函数 \(\varphi\)
- \(\varphi\)。欧拉函数有一个很著名的性质：\(\sum_{d|n}\varphi(d)=n\)。
- 与以上方法相似，咱们将它表示成狄利克雷卷积的形式：\(\varphi*I=id\)。
- 这时候，看到这个式子咱们会有一个大胆的想法，既然在这个欧拉函数与莫比乌斯函数的式子中都有\(I\)，那么咱们不如将这个式子的两边同时卷上一个\(\mu\)。
- 因而，我就能够开始填第二个坑了——欧拉函数与莫比乌斯函数的关系。
\[\varphi*I=id \\\to \varphi*I*\mu=id*\mu \\\to \varphi*\epsilon=id*\mu\]
即：\(\varphi=id*\mu \to \varphi(n)=\sum_{d|n}\mu(d)\cdot \frac{n}{d}\)
- 咱们把这个式子的两边同时除以\(n\)，则能够推出这个巧妙的式子：
\[\frac{\varphi(n)}{n}=\sum_{d|n}\frac{\mu(d)}{d}\]
（至此，我终于把莫比乌斯反演中的坑填完啦~~23333）
（有关杜教筛的前置技能也说的差很少啦，终于能够步入正题啦！）
步入正题——杜教筛
- 说了这么久，终于能够开始讲杜教筛啦！（是否是有一种莫名的兴奋呢？）
- 首先，咱们应该弄清楚一个问题：杜教筛究竟是用来干什么的？
- 杜教筛是以低于线性的时间复杂度来计算积性函数的前缀和的神奇筛法！
- 即咱们须要计算的式子为：\(\sum_{i=1}^{n}f(i)\) (\(f(i)\)为积性函数)
- PS：接下来要讲解的是杜教筛的套路式，若是不懂为何要这样作，也没有关系。只须要明白它是怎么推过来的就好了。实在看不懂就记个结论吧......
- 推式子时间到！
- 为了解决这个问题，咱们构造两个积性函数\(h\)和\(g\)。使得\(h=f*g\)
- 如今咱们开始求\(\sum_{i=1}^{n}h(i)\)。
- 记\(S(n)=\sum_{i=1}^{n}f(i)\)。
\[\sum_{i=1}^{n}h(i)=\sum_{i=1}^{n}\sum_{d|i}g(d)\cdot f(\frac{i}{d})\\\to =\sum_{d=1}^{n}g(d)\cdot\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f({i})\]
\[\to \sum_{i=1}^{n}h(i)=\sum_{d=1}^{n}g(d)\cdot S(\lfloor\frac{n}{d}\rfloor)\]
接着，咱们将右边式子的第一项给提出来，能够获得：
\[ \sum_{i=1}^{n}h(i)=g(1)\cdot S(n)+\sum_{d=2}^{n}g(d)\cdot S(\lfloor\frac{n}{d}\rfloor)\]
\[\to g(1)S(n)=\sum_{i=1}^{n}h(i)-\sum_{d=2}^{n}g(d)\cdot S(\lfloor\frac{n}{d}\rfloor)\]
其中的\(h(i)=(f*g)(i)\);
- 这就是杜教筛的惯用套路式。经各类分析，只要当你的\(h(i)\)的前缀和很好求，能在较短的时间内求出，那么当咱们对后面的式子进行整除分块时，求\(S(n)\)的复杂度为\(O(n^{\frac{2}{3}})\)
- 当咱们知道了这个套路式后，可能会思考，咱们应该如何选择这个\(g\)与\(h\)呢？
- 对于这个疑问，我没有太好的回答。只能说，依靠平时对于狄利克雷卷积中的各类式子的熟悉，以及仔细观察式子的能力啦！（固然我下面也会介绍一种小方法啦~~OVO）
- 知道了这个套路式总要练练手吧！
应用
(PS：如下例子中，假设线性筛均跑不过)jsp
一：求\(S(n)=\sum_{i=1}^{n}\mu(i)\)；函数
- 根据那个套路式：\(g(1)S(n)=\sum_{i=1}^{n}(f*g)(i)-\sum_{d=2}^{n}g(d)\cdot S(\lfloor\frac{n}{d}\rfloor)\)，咱们只须要找一个积性函数\(g\)使得这个函数与\(\mu\)的卷积的前缀和容易求。若是你认真的看了上文，应该就能够很轻松的想到一个积性函数\(I\)。
- 咱们知道\(\mu*I=\epsilon\)，很显然，单位元的前缀和很是好求，就是\(1\)，而且\(I\)十分方便整除分块。因此咱们把这个积性函数带入上述式子中能够获得：
\[S(n)=1-\sum_{d=2}^{n}S(\lfloor\frac{n}{d}\rfloor)\]
所以，咱们就学会了杜教筛莫比乌斯函数的前缀和啦！
二：求\(S(n)=\sum_{i=1}^{n}\varphi(i)\)学习
- 与求莫比乌斯函数的思路相似。
- 咱们在脑海中找到一个与欧拉函数有关的卷积式子：\(\varphi*I=id\)
- 咱们能够发现，在筛欧拉函数前缀和所选择的积性函数\(g\)一样也是\(I\)哟！代入得：
\[S(n)=\sum_{i=1}^{n}i-\sum_{d=2}^{n}S(\lfloor\frac{n}{d}\rfloor)\]
前面那个式子能够利用等差数列求和公式\(O(1)\)的计算出结果，后面一样利用整除分块。
因此，咱们又学会了如何筛欧拉函数的前缀和啦！
三：求\(S(n)=\sum_{i=1}^{n}i\cdot \varphi(i)\)优化
- 这个式子是否是没法一眼看出须要配什么积性函数了呢？
- 咱们考虑狄利克雷卷积的形式：\(\sum_{d|n}(d\cdot\varphi(d))\cdot g(\frac{n}{d})\)
- 咱们看前面这个\(d\)不太爽，考虑后面配出一个积性函数使得这个\(d\)可以被约掉。所以，咱们尝试将\(g\)配成\(id\)。这样就能够把\(d\)给弄没！代入得：
\[\sum_{d|n}(d\cdot\varphi(d))\cdot \frac{n}{d}=\sum_{d|n}n\cdot\varphi(d)\\\to=n\sum_{d|n}\varphi(d)=n^2\]
咱们惊喜的发现，彷佛配对了！！！
得：
\[S(n)=\sum_{i=1}^{n}i^2-\sum_{d=2}^{n}d\cdot S(\lfloor\frac{n}{d}\rfloor)\]
对于这个式子，咱们前面能够利用平方和的公式\(O(1)\)算出结果，后面的式子利用等差数列求和公式进行整除分块。
所以，咱们能够经过以上的思路求得这个看似没法筛的积性函数的前缀和！
代码实现
- 至于在信息学中的代码实现，我给出一个大概的思路：咱们首先先线筛出数据范围根号左右的积性函数的前缀和。再递归的实现杜教筛。
- 特别要注意的是，杜教筛筛出的前缀和必定要存下来！！！
- 若是你比较的勤劳，那就去手写hash，若是你想偷懒，那就最好用stl中的unordered_map，最好不要用map，无缘无故多个log的复杂度，何须呢......
- 还有一点，必定要记得取模！！！以及，判断要不要开long long，搞很差你TLE就是由于取模去多了，或者long long开多啦！
- 有评论区的大佬提醒我，说这份代码被卡了，我调了一下前面线筛的范围，有必定的加速，最后发现，果真是开long long的锅，如今已经将代码改正，是没有问题的啦！
- 在这里我就粘一下本身杜教筛\(\mu\)和\(\varphi\)的板子吧。这种东西最好本身手打一遍，否则你一没注意，常数一大，就很麻烦啦！（反正我写这个东西，常数巨大）
- 所以，代码仅供参考！luoguP4213杜教筛模板
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define N 6000010
using namespace std;
template<typename T>inline void read(T &x)
{
x=0;
static int p;p=1;
static char c;c=getchar();
while(!isdigit(c)){if(c=='-')p=-1;c=getchar();}
while(isdigit(c)) {x=(x<<1)+(x<<3)+(c-48);c=getchar();}
x*=p;
}
bool vis[N];
int mu[N],sum1[N],phi[N];
long long sum2[N];
int cnt,prim[N];
tr1::unordered_map<long long,long long>w1;
tr1::unordered_map<int,int>w;
void get(int maxn)
{
phi[1]=mu[1]=1;
for(int i=2;i<=maxn;i++)
{
if(!vis[i])
{
prim[++cnt]=i;
mu[i]=-1;phi[i]=i-1;
}
for(int j=1;j<=cnt&&prim[j]*i<=maxn;j++)
{
vis[i*prim[j]]=1;
if(i%prim[j]==0)
{
phi[i*prim[j]]=phi[i]*prim[j];
break;
}
else mu[i*prim[j]]=-mu[i],phi[i*prim[j]]=phi[i]*(prim[j]-1);
}
}
for(int i=1;i<=maxn;i++)sum1[i]=sum1[i-1]+mu[i],sum2[i]=sum2[i-1]+phi[i];
}
int djsmu(int x)
{
if(x<=6000000)return sum1[x];
if(w[x])return w[x];
int ans=1;
for(int l=2,r;l>=0&&l<=x;l=r+1)
{
r=x/(x/l);
ans-=(r-l+1)*djsmu(x/l);
}
return w[x]=ans;
}
long long djsphi(long long x)
{
if(x<=6000000)return sum2[x];
if(w1[x])return w1[x];
long long ans=x*(x+1)/2;
for(long long l=2,r;l<=x;l=r+1)
{
r=x/(x/l);
ans-=(r-l+1)*djsphi(x/l);
}
return w1[x]=ans;
}
int main()
{
int t,n;
read(t);
get(6000000);
while(t--)
{
read(n);
printf("%lld %d\n",djsphi(n),djsmu(n));
}
return 0;
}
总结
- 固然，杜教筛还可以筛许多东西，如：\(\sum_{i=1}^{n}i^2\cdot\mu(i)\)之类的一系列积性函数，在这里就不一一列举啦。
- 其实，通常来讲筛的就是那些经常使用的积性函数。
- 若是实在碰到相似与上面那个没法一眼看出结果的式子，咱们就能够采用刚刚例三的思路.
- 先考虑将那些特殊性质不明显的数弄掉，再尝试猜积性函数。固然不必定一试就中，可是只要咱们有足够的耐心与信念，相信这个题目所给的必定能筛，就必定能试出来233.
- 固然还有一种方法，从常见的彻底积性函数开始试，若是都不行，在尝试一下高次的彻底积性函数，以后尝试非彻底积性函数（虽然说通常都不是这个。。。），若是仍是不行，那就算了吧，（反正就那一点分么。。。），试不出，技不如人，甘拜下风233.
题目
- 题目能够去51nod上找，那上面杜教筛的题目挺多的，我就不粘地址啦！
- 洛谷上也有模板题！
- 固然，洛谷上也有须要推式子的题目，我之后有时间再加吧！