tqyaaaaang's Blog

杜教筛

来讲讲求某些积性函数前缀和的黑科技。

推荐一篇博客: 浅谈一类积性函数的前缀和

前置技能

你需要知道下列东西来理解杜教筛,这里就不详细讲了,百度一下应该会有很多的好的博客的,或者上面的博客中也有提到。

  • 数论函数
  • 积性函数
  • 常见的积性函数以及其性质 ( \(\varphi(n)\), \(\mu(n)\) )
  • 狄利克雷卷积

杜教筛

先来看一下常见的积性函数的前缀和。

\(\varphi(n)\)

令 \(\phi(n) = \sum_{i=1}^n{\varphi(i)}\)
欧拉函数的前缀和应该是最经典的了。
首先要知道 \(\sum_{d|n}{\varphi(n)} = n\)
然后就可以转化:
$$
\phi(n)
= \sum_{i=1}^n{\varphi(n)}
= \sum_{i=1}^n{(i - \sum_{d|i, d \ne i}{\varphi(d)})}
= \sum_{i=1}^n{i} - \sum_{i=1}^n { \sum_{d|i, d \ne i} {\varphi(d)} }
= \sum_{i=1}^n{i} - \sum_{d=1}^n { \sum_{i=2}^{ \lfloor \frac{n}{d} \rfloor } { \varphi(d) } } \\
= \sum_{i=1}^n{i} - \sum_{i=2}^n { \sum_{d=1}^{ \lfloor \frac{n}{i} \rfloor }{ \varphi(d) } }
= \frac { (n)*(n+1) } {2} - \sum_{i=2}^n { \phi(\lfloor \frac{n}{i} \rfloor) }
$$
然后就可以递归了。
由于\(\lfloor \frac{n}{i} \rfloor\)只有\(\Theta ( \sqrt { n } )\)种取值,故
$$
T(n) = \sum_{i=1}^{\sqrt{n}} { T(i) + T(\lfloor \frac{n}{i} \rfloor) }
$$
我们可以预处理前 \(p\) 个\(\varphi(n)\)的值,显然 \(p\) 应该至少为\(\sqrt{n}\),于是预处理为\(\Theta(p)\),再在递归的时候进行记忆化,或者直接递推,则复杂度变为了
$$
T(n) = \sum_{i=1}^{\lfloor \frac{n}{p} \rfloor} { \sqrt { \frac{n}{i} } } \approx \int_0^{\frac{n}{p}} { \sqrt { \frac{n}{x} } \rm{d} x } = \sqrt{n} \int_0^{\frac{n}{p}} { x^{-\frac{1}{2}} \rm{d} x } = \Theta ( \frac{n}{\sqrt{p}} )
$$
于是可以发现取\( p = n^{\frac{2}{3}} \)时最优,此时复杂度为\(\Theta(n^{\frac{2}{3}})\)。

\(\mu(n)\)

同理,令 \(M(n) = \sum_{i=1}^n{\mu(i)}\)
莫比乌斯函数有 \(\sum_{d|n}{\mu(i)} = [n==1]\)
于是就也可以化简了。
$$
M(n)
= \sum_{i=1}^n{\mu(n)}
= \sum_{i=1}^n{([i==1] - \sum_{d|i, d \ne i}{\mu(d)})}
= \sum_{i=1}^n{[i==1]} - \sum_{i=1}^n { \sum_{d|i, d \ne i} {\mu(d)} } \\
= 1 - \sum_{d=1}^n { \sum_{i=2}^{ \lfloor \frac{n}{d} \rfloor } { \mu(d) } }
= 1 - \sum_{i=2}^n { \sum_{d=1}^{ \lfloor \frac{n}{i} \rfloor }{ \mu(d) } }
= 1 - \sum_{i=2}^n { M(\lfloor \frac{n}{i} \rfloor) }
$$

一般情况

一般的,对应一个积性函数\(f\),如果能够找到两个函数\(g\),\(h\),使得\(f * g = h\) ( 这里 \(*\) 表示狄利克雷卷积 ) ,并且可以快速算出\(g\)的前缀和以及\(h\)的前缀和\(H\),则杜教筛可以快速计算\(f\)的前缀和\(F\)。
如上面的\(\varphi(n)\)则利用了\(\varphi * I = id\),\(\mu(n)\)则利用了\(\mu * I = e\)
那么一般情况,也可以一样的转化 ( 注意对任意积性函数\(p\)满足\( p(1) = 1 \)的性质 ) :
$$
F(n)
= \sum_{i=1}^n{f(n)}
= \sum_{i=1}^n{(h(i) - \sum_{d|i, d \ne i}{f(d)*g(\frac{i}{d})})}
= H(n) - \sum_{i=1}^n { \sum_{d|i, d \ne i} {f(d)*g(\frac{i}{d}}) } \\
= H(n) - \sum_{d=1}^n { f(d) \sum_{i=2}^{ \lfloor \frac{n}{d} \rfloor } { g(i) } }
= H(n) - \sum_{i=2}^n { g(i) \sum_{d=1}^{ \lfloor \frac{n}{i} \rfloor }{ f(d) } }
= H(n) - \sum_{i=2}^n { g(i) * F(\lfloor \frac{n}{i} \rfloor) }
$$
然后套用上面那个预处理,然后就可以做到 \(n \le 10^{11}\) 啦!

Tianqi Yang

View Comments
Navigation