杜教筛总结

综述

$$S(n) = \sum_{i = 1}^nf(i)$$

$$\sum_{i = 1}^n(f * g)(i) = \sum_{i = 1}^ng(i)S({n\over i})$$

证明

$$\sum_{i = 1}^n(f * g)(i) = \sum_{i = 1}^n \sum_{d|i}f(d)g({i\over d})$$

$$\sum_{j = 1}^ng(j)\sum_pf(p)$$

$$\sum_{i = 1}^n \sum_{d|i}f(d)g({i\over d}) = \sum_{j = 1}^ng(j)\sum_{p = 1}^{n\over j}f(p) = \sum_{i = 1}^ng(i)\sum_{d = 1}^{n\over i}f(d) = \sum_{i = 1}^ng(i)S({n\over i})$$

$$g(1)S(n) = \sum_{i = 1}^n(f * g)(i) – \sum_{i = 2}^ng(i)S({n\over i})$$

时间复杂度

$$T(n) = O(\sqrt n) + \sum_{i = 1}^\sqrt n T(i)$$

$$T(n)=\sum_{i=1}^{\sqrt{n}}{O(\sqrt{i})+O(\sqrt{\frac{n}{i}})}=O(n^\frac{3}{4})$$

$$T(n)=O(k) + \sum_{i=1}^{\frac{n}{k}}{O(\sqrt{\frac{n}{i}})}=O(\frac{n}{\sqrt{k}})$$

例子

$$S(n) = \sum_{i = 1}^n\mu(i)$$

$$S(n) = \sum_{i = 1}^n (\mu * I)(i) – \sum_{i = 2}^nI(i)S({n\over i}) = 1 – \sum_{i = 2}^nS({n\over i})$$

$$S(n) = \sum_{i = 1}^n \varphi(i)$$

$$S(n) = \sum_{i = 1}^n (\varphi * I)(i) – \sum_{i = 2}^nI(i)S({n\over i}) = {n(n + 1)\over 2} – \sum_{i = 2}^nS({n\over i})$$

bzoj4176

\large \begin{align} ans &=\sum_{i = 1}^n \sum_{j = 1}^nd(ij)\\ &= \sum_{i = 1}^n\sum_{j = 1}^n {n\over i}{n\over j}[(i,j)=1]\\ &= \sum_{i = 1}^n\sum_{j = 1}^n {n\over i}{n\over j}\sum_{d|(i,j)}\mu(d)\\ &= \sum_{d =1}^n\mu(d) \sum_{i = 1}^{n\over d}\sum_{j = 1}^{n\over d}{n\over id}{n\over jd}\\ &= \sum_{d =1}^n\mu(d) (\sum_{i = 1}^{n\over d}{{n\over d}\over i})^2\\ \end{align}
$$S(n) = \sum_{i =1}^n {n\over i}$$

$$ans=\sum_{d = 1}^n \mu(d) S({n\over d})^2$$

bzoj1968

$$f(x) = \sum_{i = 1}^x d(i)$$

$$\sum_{i = 1}^n(d*\mu)(i) = \sum_{i = 1}^n\mu(i)S({n\over i})$$

$$\mu(1)S(n) = \sum_{i = 1}^n(d * \mu)(i) – \sum_{i = 2}^n\mu(i)S({n\over i}) = n – \sum_{i = 2}^n\mu(i)S({n\over i})$$

×