杜教筛小结

写在前面

杜教筛是一种快速求积性函数前缀和的算法。
和洲阁筛一起写在『积性函数求和的几种办法』这一篇论文中，
有兴趣可以阅读一下。

前置知识

积性函数

数论函数: 指定义域为正整数、陪域为复数的函数

积性函数：对于任意互质的整数a和b有性质(f(ab)=f(a)f(b))的数论函数。

完全积性函数：对于任意整数a和b有性质(f(ab)=f(a)f(b))的数论函数。

常见的积性函数：

φ(n) －欧拉函数

μ(n) －莫比乌斯函数，关于非平方数的质因子数目

gcd(n,k) －最大公因子，当k固定的情况

d(n) －n的正因子数目

σ(n) －n的所有正因子之和

1(n) －不变的函数，定义为 1(n) = 1 （完全积性）

Id(n) －单位函数，定义为 Id(n) = n（完全积性）

ε(n) －定义为：若n = 1，ε(n)=1；若 n > 1，ε(n)=0。别称为“对于狄利克雷卷积的乘法单位”（完全积性）

λ(n) －刘维尔函数，关于能整除n的质因子的数目

摘自百度百科。

性质：$ f(n) = f(prod_{p} p_i^{k_i}) = prod f(p_i^{k_i})$

狄利克雷卷积:
两个函数(f), (g), 他们的狄利克雷卷积为: ((f * g)(n) = sum_{d | n} f(d) imes g(frac{n}{d}))
其满足交换律，结合律，分配率。
若(f),(g)是积性函数，那么(f∗g)也是积性函数。

[1 * mu = varepsilon \ 1 * varphi = Id \ mu * Id = varphi ]

然后就可以开始讲正题了：
考虑三个函数，满足： $ f * g = h ( 记他们的前缀和：) f:F, g:G, h: H$
那么：

[H(x) = sum_{n = 1} ^ {x} h(n) \ = sum_n sum_ {d | n} f(d)g(frac{n}{d}) \ = sum_{d = 1}^{x} sum_{n = 1}^{lfloor frac{x}{d} floor} f(d)g(n)\ = sum_{d = 1}^{x} f(d) sum_{n = 1}^{lfloor frac{x}{d} floor} g(n)\ = sum_{d = 1}^{x} f(d)G(lfloor frac{x}{d} floor) \ = sum_{d = 1}^{x} g(d)F(lfloor frac{x}{d} floor) \ g(1)F(n) = H(n) - sum_{d = 2}^{x} g(d)F(lfloor frac{x}{d} floor) ]

只要能快速求出H(n), g(d)(然后就可以(O(n ^ frac{2}{3})) 简单的求出(F(n)))

Example:

求$$sum_{i = 1}^{n} varphi(i) ~~ sum_{i = 1}^{n} mu(i)$$

---

[sum_{n = 1}^{x} varphi(n) = frac{x * (x + 1)}{2} - sum_{i = 2}^{x}varphi(lfloor frac{x}{i} floor) \ sum_{n = 1}^{x} mu(n) = 1 - sum_{i = 2}^{x}mu(lfloor frac{x}{i} floor) ]