首页 > 笔记 > 杜教筛总结

杜教筛总结

糖教 orz

前置莫比乌斯反演进阶总结

综述

有数论函数$f(n)$,求

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

那么对于任意数论函数$g(n)$,满足

$$\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})$$

考虑枚举$j = {i\over d}$,那么就是

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

考虑如何枚举$p$呢?也就是我们固定了$i\over d$,再考虑所有对它造成贡献的$d$

这样我们就可以考虑枚举一层$d$(换字母成$p$),那就能得出$i = pj$,我们可以想到,只要这里的$i \leq n$,这个$p$就是合法的。。这样就限制了$p$枚举的上界也就是$n\over j$,这样得出:

$$\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})$$

一般找的$g(n)$是个积性函数或者常函数,$g(1)$一般都是1,而且意味着$f * g$和$g$也是很好求和的函数。

这样可以看到这个式子可以整除分块

总的来说

如果能通过狄利克雷卷积构造一个更好计算前缀和的函数,且用于卷积的另一个函数也易计算,则可以简化计算过程

时间复杂度

假如算出$f(n)$的复杂度是$T(n)$,那么

$$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})$$

积性函数的话,我们可以用线性筛来预处理前$k$个的答案,就变成了

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

这样就发现了$k = n^{2\over 3}$的时候最优,$T(n) = O(n^{2\over 3})$

例子

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

卷个$I(n)$(恒等函数:$I(n) = 1$),得到$\mu * I = e$(狄利克雷卷积的乘法单位元,$e(n) = [n =1 ]$)

$$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)$$

卷个$I(n)$,得到$\varphi * I = id$(单位函数:$id(n) = n$)

$$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})$$

bzoj3944

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)$$

由于$d * \mu = 1$

通式:

$$\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})$$

由于数据范围小,没筛$d$,直接$O(n^{3\over 4})$。。


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×