关于数论分块时间复杂度和算法正确性的详细证明

数论分块块长结论：对于正整数 $n>p$，$\forall 正整数i\land \lfloor n/p \rfloor=\lfloor n/i \rfloor,i\le\lfloor \frac{n}{\lfloor n/p\rfloor}\rfloor$。

证明：①当 $p\le \sqrt n$ 时：

结论 a：$\forall 正整数i\le \sqrt n,\lfloor n/i \rfloor \neq \lfloor \frac{n}{i+1} \rfloor$。

a. 证明：反证，假设 $\exist 自然数i\le \sqrt n,\lfloor n/i \rfloor = \lfloor \frac{n}{i+1} \rfloor$。设 $n=ik+s,s<i,n=(i+1)k+p,p<i+1$。所以 $n=ik+k+p=n-s+k+p$，进而 $k+p=s$。由于 $k\ge \sqrt n\ge i>s$，所以 $k>s,p\ge0$。矛盾，证毕。

由结论 a 可得，问题变为证明 $\lfloor \frac{n}{\lfloor n/p\rfloor}\rfloor=p$。设 $\lfloor n/p \rfloor=k$，即证 $\lfloor n/k \rfloor=p$。设 $n=pk+s$，由 $\lfloor n/p \rfloor=k$ 得 $s<p$，由于 $p\le\sqrt n\le k$ 所以 $n=(p+t)k+w,w<k,正整数t\ge0$。如法炮制：$n=pk+tk+w=n-s+tk+w$ 得到 $-s+tk+w=0$。所以 $tk=s-w$。注意到 $s,w$ 都是余数，所以 $s-w\le s<p\le k$，$s-w<k$。显然 $t=0$，得 $w=s$。式子 $n=(p+t)k+w,w<k$ 的意义就是 $\lfloor n/k \rfloor=p+t=p$。

②当 $p>\sqrt n$ 时：

令 $i=\lfloor \frac{n}{\lfloor n/p\rfloor}\rfloor$，即证 $\lfloor n/p \rfloor=\lfloor n/i \rfloor,\lfloor n/p \rfloor\neq\lfloor \frac{n}{i+1} \rfloor$。继续设 $\lfloor n/p \rfloor=k$，即证 $k=\lfloor n/i \rfloor=\lfloor\frac{n}{\lfloor n/k \rfloor}\rfloor,k\neq\lfloor \frac{n}{\lfloor n/k \rfloor+1} \rfloor$。由①可知，$\forall p\le \sqrt n,\lfloor \frac{n}{\lfloor n/p\rfloor}\rfloor=p$。结合 $k<\sqrt n$ 可知 $k=\lfloor\frac{n}{\lfloor n/k \rfloor}\rfloor$ 成立。问题变为证明 $\lfloor\frac{n}{\lfloor n/k \rfloor}\rfloor\neq\lfloor\frac{n}{\lfloor n/k \rfloor+1}\rfloor$。设 $x=\lfloor n/k \rfloor$，即证 $\lfloor\frac{n}{x}\rfloor\neq\lfloor\frac{n}{x+1}\rfloor$。反证，假设 $\lfloor\frac{n}{x}\rfloor=\lfloor\frac{n}{x+1}\rfloor=m$。则 $\frac{n}{x+1}\in[m,m+1),n/x\in[m,m+1)$。变形得 $n\in[m(x+1),x(m+1))$。同理由 $n/k\in(x,x+1)$ 可得 $n\in[kx,k(x+1))$，即 $m(x+1)<k(x+1),kx<x(m+1)$，得 $k\in(m,m+1)$，这样的 $k$ 不存在，矛盾，假设不成立。

综上证毕。

数论分块的时间复杂度为 $O(\sqrt n)$。

证明：即证 $\lfloor n/i \rfloor$ 的取值数量的数量级为 $\sqrt n$。对于 $i\le \sqrt n$，由结论 a 可得每一个 $i$ 对应一个 $\lfloor n/i \rfloor$。对于 $i>\sqrt n$，$\lfloor n/i \rfloor\in[1,\sqrt n)$。所以总共不超过 $2\sqrt n$ 种。证毕。