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

· · 算法·理论

参考

虽然上面那篇文章把该讲的东西都讲了，但其实看得很费劲。

数论分块块长结论：对于正整数 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 种。证毕。