转载自：腾讯云 - 杜教筛入门
ps：其实我就是看看里面的公式，原文公式不显示了。
Orz OO0OOO00O0OOO0O00OOO0OO - 杜教筛的发明者
前置知识
狄利克雷卷积
杜教筛
套路
杜教筛是用来求一类积性函数的前缀和
它通过各种转化，最终利用数论分块的思想来降低复杂度
假设我们现在要求(S(n) = sum_{i = 1}^n f(i))，(f(i))为积性函数,(n leqslant 10^{12})
直接求肯定是不好求的，不过现在假设有另一个积性函数(g)
我们来求它们狄利克雷卷积的前缀和
[(g * f) = sum_{i = 1}^n sum_{d mid i} g(d) f(frac{i}{d})
]
[= sum_{d = 1}^n g(d) sum_{d|i} f(frac{i}{d})
]
[= sum_{d = 1}^n g(d) sum_{i = 1}^{frac{n}{d}}f(i)
]
[= sum_{d = 1}^n g(d) S(frac{n}{d})
]
然后就化不动了，不过我们发现我们化出了(frac{n}{d})！excited
但是(S(n))怎么求呢？
容斥一下
[g(1)S(n) = sum_{d = 1}^n g(d)S(frac{n}{d}) - sum_{d = 2}^n g(d)S(frac{n}{d})
]
前半部分是狄利克雷卷积的前缀和的形式
后半部分可以数论分块。这样看起来就好搞多了
现在我们的问题是，如何选择(g)才能使得上面这个式子好算
这个就要因情况而定了
下面煮几个典型栗子
(mu)函数
定理:(sum_{d mid n} mu(d) = [n = 1])
那么我们如果选择(g = e)，(e)为原函数，(e = [n = 1])
(g)与(mu)的卷积的前缀和肯定为(1)
上面的式子变为
(S(n) = 1 - sum_{d = 2}^n S(frac{n}{i}))
后半部分直接数论分块就好
(varphi)函数
定理：(sum_{d mid n}varphi(d) = n)
我们的(g)还是选(e)做卷积
我们要求得式子变为
[S(n) = frac{n * (n + 1)}{2} - sum_{d = 2}^n S(frac{n}{i})
]
前半部分(O(1))算，后半部分数论分块