A simple Blog for wyx I've been down the bottle hoping.
杜教筛的推导指南
发表于: | 分类: Oi | 评论:0 | 阅读:100

考试之前写题解据说能加RP??

杜教筛专门用来对一类积性函数求和。

举个例子 $\mu(i)$ $\phi(i)$ 就是积性函数

我们现在假设求

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

然后我们令 $g(i) = \mu(i), f(i)=\sum_{d|i}g(d)$

那么我们考虑 $\sum_{i=1}^n{f(i)}$

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

$\sum_{d=1}^n{f(d) \lfloor \frac{n}{d} \rfloor}$

$\sum_{d=1}^n{f(d) \sum_{i=1}^n [i\le \frac{n}{d}]}$

$\sum_{i=1}^n{\sum_{d=1}^n{f(d)[d\le \frac{n}{i}]}}$

$\sum_{i=1}^n{G(\frac{n}{i})}$

我们考虑我们要求的是 $G(n) = G(\frac{n}{1})$

然后?

$\sum_{i=1}^n{f(i)} = \sum_{i=1}G(\frac{n}{i}) = G(1) +\sum_{i=2}G(\frac{n}{i})$

注意到 $f(i)$ 是可以直接 $O(1)$ 算的, 因为

$\sum_{i=1}^n \sum_{d|i}^n{\mu(d)} = n$,

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

所以移项之后直接套用即可,当然我们需要预处理一部分

可以知道当前后复杂度相同的时候取到复杂度谷值,通过积分得知复杂度为 $O(n^{\frac{2}{3}})$

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP