杜教筛
作用：用来求积性函数前缀和，时间复杂度为(O(n^frac{2}{3}))
积性函数
若对于函数 (f(x)) 满足 (f(x)=f(a)*f(b)) ，其中 (x=a*b) 且 (gcd(a,b)=1)，那么 (f(x)) 为积性函数。
常见积性函数：
- (mu()) ——莫比乌斯函数。
- (phi()) ——欧拉函数。(phi(n)=sum_{i=1}^n [gcd(n,i)=1])
- (d()) ——约数个数。(d(n)=sum_{i=1}^n[i|n])
- (sigma()) ——约数和函数。(sigma(n)=sum_{i=1}^n[i|n]*i)
积性函数中的特殊存在完全积性函数，即不需满足 (gcd(a,b)=1) 的积性函数。
常见的完全积性函数：
- $ epsilon()$ ——元函数。$ ϵ(n)=[n=1]$
- (I()) ——恒等函数。(I(n)=1)
- (id()) ——单位函数。(id(n)=n)
狄利克雷卷积，假设符号为 (*)
定义：两个数论函数的狄利克雷卷积为 ((f*g)(n)=sum_{d|n} f(d)*g(frac{n}{d}))
很显然，狄利克雷卷积满足以下运算规律：
- 交换律 ((f∗g=g∗f))
- 结合律 (((f∗g)∗h=f∗(g∗h)))
- 分配律 (((f+g)∗h=f∗h+g∗h))
举例：对于数论函数 (f) ，(f=f*epsilon)
杜教筛
假设我们要计算 (sum_{i=1}^n f(i)) ((f(i))为积性函数)
第一步： 构造两个积性函数 (h) 和 (g) ，使得 (h=f*g)
第二部：推式子，设 (S(n)=sum_{i=1}^n f(i))
接着，我们将右边式子的第一项给提出来，可以得到：
这样的话，(S(n)) 就可以递归求解。
对于积性函数 (h) 和 (g) 选择要靠自己总结。
小试身手
假如我们要求的 (f) 函数为 (mu) ，显然 (epsilon=mu*I) ，即 (h) 函数为 (epsilon) ，(g) 函数为 (I)
代入到上面杜教筛的式子中，(I(1)*S(n)=sum_{i=1}^nepsilon(i)-sum_{d=2}^n I(d)*S(leftlfloorfrac{n}{d} ight floor))
即 (S(n)=1-sum_{d=2}^n S(leftlfloorfrac{n}{d} ight floor)) ，(leftlfloorfrac{n}{d} ight floor) 明显可以整除分块。
整除分块、记忆化搜索即可。
假如我们要求的 (f) 函数为 (phi) ，显然 (id=phi*I) ，即 (h) 函数为 (id) ，(g) 函数为 (I)
代入到上面杜教筛的式子中，(I(1)*S(n)=sum_{i=1}^nid(i)-sum_{d=2}^n I(d)*S(leftlfloorfrac{n}{d} ight floor))
即 (S(n)=frac{(n+1)*n}{2}-sum_{d=2}^n S(leftlfloorfrac{n}{d} ight floor)) ，(leftlfloorfrac{n}{d} ight floor) 明显可以整除分块。
整除分块、记忆化搜索即可。
假如我们要求的 (f) 函数为 (d) (约数个数函数) ，用莫反推得 (I=d*mu) ，即 (h) 函数为 (I) ，(g) 函数为 (mu)
代入到上面杜教筛的式子中，(mu(1)*S(n)=sum_{i=1}^nI(i)-sum_{d=2}^n mu(d)*S(leftlfloorfrac{n}{d} ight floor))
即 (S(n)=n-sum_{d=2}^n mu(d)*S(leftlfloorfrac{n}{d} ight floor)) ，(mu) 前缀和可以再用一次杜教筛。
整除分块、记忆化搜索即可。
总结：杜教筛思维上并不是很难，但需要基础数论知识较多。