部分数论知识点证明补充 | qkoqhh

参考链接

https://riteme.site/blog/2018-9-11/time-space-complexity-dyh-algo.html

前言

这篇主要是用来补充一些知识点的证明，会用不会证明可不行，做数学当然得注重证明过程

数论分块

定义 $R(n)$ 为正整数集 ${\lfloor\frac{n}{d}\rfloor\mid1\le d\le n}$

我们知道 $|R(n)|=O(\sqrt n)$ ，因此对这类的和式可以分块求和处理。

之前有道题让我研究过， $\lfloor\frac{n}{d} \rfloor$ 的分布分为前 $\sqrt n$ 和后 $\sqrt n$ ，即前 $\sqrt n$ 个结果分布得比较稀疏，而 $1$ ~ $\sqrt n$ 均会在后 $\sqrt n$结果中出现。

定理1 令 $\lfloor\frac{n}{d}\rfloor=k$ 成立的最大的 $d$ 为 $\lfloor\frac{n}{k} \rfloor$ ，最小的 $d$ 为 $\lfloor\frac{n}{k+1} \rfloor+1$

证明

若 $\lfloor\frac{n}{d}\rfloor=k$ ，则

$dk\le n <d(k+1)$

则 $d$ 需满足

$\begin{aligned} d\le&\frac{n}{k}\\ d>&\frac{n}{k+1} \end{aligned}$

由于 $d$ 为整数，有

$\begin{aligned} d_{max}&=\lfloor\frac{n}{k}\rfloor\\ d_{min}&=\lfloor\frac{n}{k+1} \rfloor+1 \end{aligned}$

那么分块时直接根据答案 $k$ 来决定块的上下界即可

定理2 $\forall n,m\in \mathbb{N}$ ，若 $m\le\sqrt n$ ，则 $\lfloor n/\lfloor n/m\rfloor\rfloor=m$

证明

令 $k=\lfloor\frac{n}{m} \rfloor$ ，有

$\begin{eqnarray*} mk&\le n&<m(k+1)\\ m&\le \frac{n}{k}&<\frac{m(k+1)}{k} \end{eqnarray*}$

那么，若要 $\lfloor\frac{n}{k} \rfloor=m$ ，要 $\frac{m(k+1)}{k}\le m+1$ ，即 $m\le k=\lfloor\frac{n}{m} \rfloor$ ，即 $m\le \sqrt n$

定理3 $|R(n)|=2\sqrt n+\Theta(1)$

证明

当 $d< \sqrt n$ 时，$\lfloor\frac{n}{d} \rfloor$ 对应不同的结果，对应前 $\sqrt n$ 个结果，此时 $\lfloor\frac{n}{d} \rfloor>\sqrt n$

当 $d\ge \sqrt n$ 时，令 $k=\lfloor\frac{n}{d} \rfloor$ ，则 $k\le \sqrt n$ ，那么后 $\sqrt n$ 最多只有 $\sqrt n$ 个结果，由定理 $2$ 可知，对 $\forall k\le\sqrt n$ ，只要令 $d=\lfloor\frac{n}{k} \rfloor$ ，即可得到 $\lfloor\frac{n}{d} \rfloor=k$

定理4 $\forall n\in \mathbb{N},\forall m\in R(n),R(m)\subseteq R(n)$

证明令 $m=\lfloor\frac{n}{k}\rfloor$ ，则 $\lfloor\frac{m}{d}\rfloor=\lfloor\frac{\lfloor\frac{n}{k}\rfloor}{d}\rfloor=\lfloor\frac{n}{kd}\rfloor$ ，则 $\lfloor\frac{m}{d}\rfloor\in R(n)$

杜教筛复杂度证明

之前看的 $tls$ 的博客确实没有看懂复杂度的证明，这里就根据参考文章给出杜教筛的复杂度证明(但并不同意 $tls$ 的证明是自欺欺人，肯定是窝太菜了)

从复杂度证明的角度看，杜教筛实际上是个分块套分块，所以直接对每个块的复杂度求个和即可

$\begin{aligned} T(n)&=\sum_{k\in R(n)}O(\sqrt k) \\&=\sum_{k=1}^{\sqrt n}O(\sqrt k)+\sum_{k=1}^{\sqrt n}O(\sqrt{\frac{n}{k}}) \\&= O(\int_0^{\sqrt n}\sqrt xdx+\int_0^{\sqrt n}\sqrt{\frac{n}{x}}dx ) \\&=O(n^{\frac{3}{4} }) \end{aligned}$

如果加上预处理，那么设预处理的复杂度为 $O(n)$ ，预处理的规模为 $S$ $(S\ge\sqrt n)$ ，那么有

$\begin{aligned} T(n)&=O(S)+\sum_{i=1}^{n/k>S}O(\sqrt{\frac{n}{k}}) \\&=O(S)+O(\sqrt n\sqrt{\frac{n}{S}}) \\&\ge O(n^{\frac{2}{3}}) \end{aligned}$

当且仅当 $S=n^{\frac{2}{3}}$ 时， $T(n)$ 最小