【算法】杜教筛

杜教筛是一种简化运算的方式,运用狄利克雷卷积来优化函数前缀和的计算

例子

已知

$$ \sum_{d|n}\phi(d)=n $$

对其进行变换

$$ \sum_{d|n}\phi(d)=n\\ \frac{n(n+1)}{2}=\sum_{i=1}^{n}\sum_{d|i}\phi(d)\\ \frac{n(n+1)}{2}=\sum_{d=1}^{n}\sum_{i=1}^{\frac{n}{d}}\phi(d) $$

令 $S(n)=\sum_{i=1}^n\phi(i)$, 可得

$$ \frac{n(n+1)}{2}=\sum_{d=1}^{n}\sum_{i=1}^{\frac{n}{d}}\phi(d)=\sum_{d=1}^{n}\sum_{i=1}^{\frac{n}{d}}\phi(i)=\sum_{d=1}^{n}S(\frac{n}{d})\\ S(n)=\frac{n(n+1)}{2}-\sum_{d=2}^{n}S(\frac{n}{d}) $$

然后对于 $\frac{n}{d}$ 进行分块然后递归操作即可
当然,也可以将 $S(1)-S(n^{\frac{2}{3}})$ 预处理处理出来,这样复杂度可以优化到 $O(n^{\frac{2}{3}})$

$tips:$

为啥 $\sum_{d=1}^{n}\sum_{i=1}^{\frac{n}{d}}f(d)=\sum_{d=1}^{n}\sum_{i=1}^{\frac{n}{d}}f(i)$ 呢

因为 $\sum_{i=1}^{n}[\frac{n}{i}\ge x]=\frac{n}{x}$

(逃

Comments

添加新评论