杜教筛学习笔记

对于数论函数 \(f\)，记 \(S_f(n)=\sum_{k=1}^nf(k)\)。

记 \(R(n)=\{\lfloor\frac{n}{d}\rfloor:d\in \mathbb{Z}^+\wedge d\le n\}\)。

引理：

\[|R(n)|\le2\sqrt{n} \]

证明：\(d\le\sqrt{n}\) 的数不超过 \(\sqrt{n}\) 个。对于 \(d>\sqrt{n}\)，\(\lfloor\frac{n}{d}\rfloor<\sqrt{n}\)，同样不超过 \(\sqrt{n}\) 个。

称 \(S_f\) 为在 \(R(n)\) 中每个点上的值为 \(f\) 对于 \(n\) 的块筛。

杜教筛可以对于几类特殊数论函数，\(O(n^{\frac{3}{4}})\) 或 \(O(n^{\frac{2}{3}})\) 地算出其块筛。

Dirichlet 乘法

\(f,g,h\) 是满足 \(f*g=h\) 的数论函数，已知 \(f,g\) 的块筛，求 \(h\) 的块筛。

\[\begin{align} S_h(n)&=\sum_{k=1}^nh(k)\\ &=\sum_{k=1}^n(f*g)(k)\\ &=\sum_{k=1}^n\sum_{d|k}f(\frac{n}{d})g(d)\\ &=\sum_{d=1}^ng(d)\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}f(k)\\ &=\sum_{d=1}^ng(d)S_f(\lfloor\frac{n}{d}\rfloor) \end{align} \]

数论分块计算，求单点是 \(O(\sqrt{n})\) 的。

将 \(R(n)\) 中每个点单独计算。

对于 \(d>\sqrt{n}\)，\(\lfloor\frac{n}{d}\rfloor<\sqrt{n}\)。一次 \(O(n^{\frac{1}{4}})\)，共 \(O(n^{\frac{3}{4}})\)。

对于 \(d\le\sqrt{n}\)：

\[\begin{align} \sum_{d=1}^{\lfloor\sqrt{n}\rfloor}\sqrt{\frac{n}{d}}&=\sqrt{n}\sum_{d=1}^{\lfloor{\sqrt{n}}\rfloor}d^{-\frac{1}{2}}\\ &\le\sqrt{n}\int_0^{\sqrt{n}}x^{-\frac{1}{2}}{\rm d}x\\ &=2n^{\frac{3}{4}} \end{align} \]

故块筛是 \(O(n^{\frac{3}{4}})\) 的。

Dirichlet 乘法*

很多时候可以快速求出 \(h\) 前 \(m\) 项的值，这里假设可以 \(O(m)\) 计算 \(h\) 前 \(m\) 项的值。

分块。对于 \(\lfloor\frac{n}{d}\rfloor\le m\) 的点预处理，其他不变。

\[\begin{align} m+\sum_{d=1}^{\lfloor\frac{n}{m}\rfloor}\sqrt{\frac{n}{d}}&=m+\sqrt{n}\sum_{d=1}^{\lfloor\frac{n}{m}\rfloor}d^{-\frac{1}{2}}\\ &\le m+\sqrt{n}\int_0^\frac{n}{m}x^{-\frac{1}{2}}{\rm d}x\\ &=m+\frac{2n}{\sqrt{m}} \end{align} \]

故取 \(m=n^{\frac{2}{3}}\) 时复杂度降为 \(O(n^{\frac{2}{3}})\)。

Dirichlet “除法”

\(f,g,h\) 是满足 \(f*g=h\) 的数论函数，已知 \(g,h\) 的块筛，求 \(f\) 的块筛。

\[\begin{align} S_h(n)&=\sum_{d=1}^ng(d)S_f(\lfloor\frac{n}{d}\rfloor)\\ &=g(1)S_f(n)+\sum_{d=2}^ng(d)S_f(\lfloor\frac{n}{d}\rfloor)\\ S_f(n)&=\frac{S_h(n)-\sum_{d=2}^ng(d)S_f(\lfloor\frac{n}{d}\rfloor)}{g(1)} \end{align} \]

按 \(d\) 的递减序计算时，查询 \(S_f(\lfloor\frac{n}{d}\rfloor)\) 可以做到 \(O(1)\) 。其余复杂度分析同乘法部分，是 \(O(n^{\frac{3}{4}})\) 的。

Dirichlet “除法”*

假设可以 \(O(m)\) 计算 \(f\) 前 \(m\) 项的值。取 \(m=n^{\frac{2}{3}}\)，分块后可以做到 \(O(n^{\frac{2}{3}})\)。