本系列是这本算法教材的扩展：《算法竞赛入门到进阶》(

  杜教筛用途：在低于线性时间里，高效率求一些积性函数的前缀和。   杜教筛算法 = 整除分块 + 狄利克雷卷积 + 线性筛。   杜教筛公式：\(g(1)S(n)=\sum_{i=1}^nh(i)-\sum_{i=2}^ng(i)S(\lfloor\frac{n}{i}\rfloor)\)

  “杜教筛”，一个亲切的算法名字，从2016年后流行于中国的OI圈。    杜教，即信息学竞赛的大佬杜瑜皓。本文作者好奇“杜教筛”这个名称的来源，在QQ上联系到他，他说，虽然算法的原理不是他的发明，但确实是他最早应用在OI竞赛中。至于为什么被称为“杜教筛”并广为传播，可能是一个迷了。   这个算法的原始出处，据skywalkert（唐靖哲，唐老师）的博客说，“这种黑科技大概起源于Project Euler这个网站，由xudyh（杜瑜皓）引入中国的OI、ACM界，目前出现了一些OI模拟题、OJ月赛题、ACM赛题是需要这种技巧在低于线性时间的复杂度下解决一类积性函数的前缀和问题。”   Project Euler网站也是一个OJ，题库里面有很多高难度的数学题。不过这个OJ并不需要提交代码，只需要提交答案即可。这个网站被推崇的一大原因是：如果提交的答案正确，就有权限看别人对这一题的解题方法，以及上传的代码。   经典的杜教筛题目，例如洛谷P4213，求数论函数的前缀和。

  题目中的\(\phi(i)\)是欧拉函数，\(\mu(i)\)是莫比乌斯函数。欧拉函数、莫比乌斯函数在算法竞赛中很常见，它们都是积性函数。题目求这2个积性函数的前缀和，由于给的n很大，显然不能直接用暴力的、复杂度\(O(n)\)的线性方法算，需要用杜教筛，复杂度是\(O(n^{\frac23})\)。   读者看到\(O(n^{\frac23})\)，可能感觉和\(O(n)\)相差不大，但实际上是一个很大的优化，两者相差\(n^{\frac13}\)倍。在上面的例题中，\(n\)=21亿，\(n^{\frac23}\)=160万，两者相差1300倍。   关于“杜教筛”的理论知识介绍，影响较大的有：   （1）2016年信息学奥林匹克中国国家队候选队员论文集，“积性函数求和的几种方法 任之洲”，其中提到杜教筛：“这个算法在国内信息学竞赛中一般称为杜教筛，可以高效地完成一些常见数论函数的计算。”   （2）2016年，skywalkert（唐老师）的博客。

  由于杜教筛涉及的知识比较多，不容易讲清楚。所以本文将循循善诱地完成这一困难的任务，本文的顺序是：   （1）积性函数的定义和一些性质。积性函数的常见计算。   （2）以欧拉函数为例，讲解积性函数的计算。欧拉函数有什么用、如何求、它的求解和积性函数有什么关系、为什么用到杜教筛。   （3）整数分块。   （4）狄利克雷卷积。   （5）莫比乌斯函数和莫比乌斯反演。   （6）杜教筛。杜教筛公式、复杂度证明、欧拉函数和莫比乌斯函数的杜教筛实现。

  如果读者没有深入学过数论，第一次看到这些词语：积性函数、欧拉函数、狄利克雷卷积、莫比乌斯函数、莫比乌斯反演、杜教筛，是不是感到高深莫测、头皮发怵？   即使读者学过一些数论，但是还没有系统读过初等数论的书，那么在阅读本文之前，最好也读一本，比如《初等数论及其应用》Kenneth H.Rosen著，夏鸿刚译，机械工业出版社。这本书很易读，非常适合学计算机的人阅读：（1）概览并证明了初等数论的理论知识；（2）理论知识的各种应用，可以直接用在算法题目里；（3）大量例题和习题；（4）与计算机算法编程有很多结合。花两天时间通读很有益处。   本文所有的数学定义都引用自这本书。

  定义[《初等数论及其应用》第7章乘性函数]：

  （1）定义在所有正整数上的函数称为算术函数（或数论函数）。   （2）如果算术函数f对任意两个互质（互素）的正整数\(p\)和\(q\)，均有\(f(pq)=f(p)f(q)\)，称为积性函数（multiplicative functions，或译为乘性函数）[有乘性函数，也有加性函数，参考《初等数论及其应用》182页]。

  （3）如果对任意两个正整数\(p\)和\(q\)，均有\(f(pq)=f(p)f(q)\)，称为完全积性函数。   性质： 【定理1.1】 积性函数的和函数也是积性函数。如果\(f\)是积性函数，那么\(f\)的和函数\(F(n)=\sum_{d|n}f(d)\)也是积性函数。   其中\(d|n\)表示\(d\)整除\(n\)。   和函数在杜教筛中起到了关键的作用。

  （1）计算积性函数\(f\)的第\(n\)项\(f(n)\)。   （2）计算积性函数\(f\)在\(1～n\)范围内所有项：\(f(1)、f(2)、\cdots 、f(n)\)。   （3）计算积性函数\(f\)前\(n\)项的和：\(\sum_{i=1}^nf(i)\)，即前缀和。这就是杜教筛的目标。   后面以欧拉函数和莫比乌斯函数为例，解答了这几个问题。

  下面的积性函数，在狄利克雷卷积中常常用到。   \(I(n)\)：恒等函数，\(I(n)=1\)   \(id(n)\)：单位函数，\(id(n)=n\)   \(I_k(n)\)：幂函数，\(I_k(n)=n^k\)   \(\epsilon(n)\)：元函数，\(\epsilon(n)= \begin{cases} 1, & \text {n=1} \\ 0, & \text{n>1} \end{cases}\)   \(\sigma(n)\)：因子和函数，\(\sigma(n)=\sum_{d|n}d\)   \(d(n)\)：约数个数，\(d(n)=\sum_{d|n}1\)

  为了彻底了解积性函数的运算，本节以欧拉函数为例进行讲解，这是一个经典的积性函数。并用这个例子引导出为什么要使用杜教筛。

  定义：设n是一个正整数，欧拉函数\(\phi(n)\)定义为不超过\(n\)且与\(n\)互质的正整数的个数。   定义用公式表示：\(\phi(n)=\sum_{i=1}^n[gcd(i,n)=1]\)   例如：   n = 4时，1、3这2个数与4互质，\(\phi(4)=2\)；   n = 9时，1、2、4、5、7、8这6个数与9互质，\(\phi(9)=6\)。 【定理2.1】 [有关欧拉函数的所有证明，见《初等数论及其应用》176-180页]: 设p和q是互质的正整数，那么\(\phi(pq)=\phi(p)\phi(q)\)。

  这个定理说明欧拉函数是一个积性函数。有以下推理：   若\(n=p_1^{a_1}\times p_2^{a_2}\times \cdots\times p_s^{a_s}\)，其中\(p_1、p_2、\cdots、p_s\)互质，\(a_1、a_2、\cdots、a_s\)是它们的幂，则\(\phi(n)=\phi(p_1^{a_1}) \times \phi(p_2^{a_2}) \times \cdots\times\phi(p_s^{a_s}) )\) 。   如果\(p_1、p_2、...、p_s\)互质，那么\(p_1^{a_1}、p_2^{a_2}、\cdots、p_s^{a_s}\)也是互质的。   以\(n = 84\)为例：   \(84=2^2 \times 3 \times 7\)   \(\phi(84)=\phi(2^2 \times 3 \times 7)=\phi(2^2) \times \phi(3) \times \phi(7))\) 【定理2.2】 设\(n\)为正整数，那么\(n=\sum_{d|n}\phi(d)\)   其中\(d|n\)表示\(d\)整除\(n\)，上式对\(n\)的正因子求和。 例如\(n=12\)，那么\(d\)是\(1、2、3、4、6、12\)，有：\(12=\phi(1)+\phi(2)+\phi(3)+\phi(4)+\phi(6)+\phi(12)\)   这个定理说明了n与的\(\phi(n)\)关系：\(n\)的正因子（包括\(1\)和自身）的欧拉函数之和等于\(n\)。   有很多方法可以证明，这里给出一种直接易懂的证明。   证明：分数\(\frac 1n,\frac 2n,\cdots,\frac nn\)，共有\(n\)个，且互不相等。化简这些分数，得到新的\(n\)个分数，它们的分母和分子互质，形如\(\frac ad\)，\(d|n\)且\(a\)与\(d\)互质。在所有\(n\)个分数中，分母为\(d\)的分数，数量是\(\phi(d)\)。所有不同分母的分数，其总数是\(\sum_{d|n}\phi(d)\)，所以\(n=\sum_{d|n}\phi(d)\)，得证。   定理2.2是欧拉函数特别重要的一个性质，这一性质被用到了杜教筛中。

  欧拉函数有什么用呢？利用它可以推出欧拉定理[欧拉定理：设\(m\)是一个正整数，\(a\)是一个整数且\((a, m)=1\)，那么\(a^{\phi(m)}\equiv1(mod\ m)\)]，欧拉定理可用于：求大数的模、求解线性同余方程等，在密码学中有重要应用。所以求\(\phi(n)\)是一个常见的计算。   从定理2.1可以推出定理2.3，定理2.3是计算\(\phi(n)\)的通解公式。 【定理2.3】 设：\(n=p_1^{a_1}\times p_2^{a_2}\times \cdots\times p_s^{a_s}\)为正整数\(n\)的质幂因子分解，那么：

  上述公式，有两个特殊情况：   （1）若\(n\)是质数，\(\phi(n)=n-1\)。这一点很容易理解，请读者思考。   （2）若\(n=p^k\)，\(p\)是质数，有：\(\phi(n)=\phi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)=p^{k-1}\phi(p)\)   这两种情况将用于2.3.2节编程求欧拉函数。   所以，欧拉函数\(\phi(n)\)的求解，归结到了分解质因子这个问题。分解质因子有一个古老的方法，试除法[试除法很低效，有很多快速分解质因子的方法，参考《初等数论及其应用》93页]：求\(n\)的质因子时，逐个检查从\(2\)到\(\sqrt{n}\)的所有质数，如果它能整除\(n\)，就是一个因子。试除法的复杂度是\(O(\sqrt{n})\)，效率很低。在密码学中，有高达百位以上的十进制数分解质因子，因此发明了很多高效率的方法。不过，在算法竞赛中，数据规模不大，所以一般就用试除法。   下面是求欧拉函数的代码。先用试除法分解质因子，再用公式\(\phi(n)=n \prod_{i=1}^k(1-\frac 1{p_i})\)求得\(\phi(n)\)。总复杂度仍然是\(O(\sqrt{n})\)。

  （2）自己推导[引用]