关于数论分块的证明

证明借鉴：
1.借鉴1
2.训练指南数论公因数部分
当 i∈[1,n]i\in[1,n]i∈[1,n] 时，
⌊ni⌋=⌊n⌊n⌊ni⌋⌋⌋\lfloor\frac{n}{i}\rfloor=\lfloor\frac{n}{\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor}\rfloor⌊in​⌋=⌊⌊⌊in​⌋n​⌋n​⌋
同时, ⌊ni⌋\big\lfloor\frac{n}{i}\big\rfloor⌊in​⌋ 的取值最多有 2n2\sqrt n2n​ 个
证明1：
设 ⌊ni+Δ⌋=⌊ni⌋=k\lfloor\frac{n}{i+\Delta}\rfloor=\lfloor\frac{n}{i}\rfloor=k⌊i+Δn​⌋=⌊in​⌋=k
设 ki+p=n,k(i+Δ)+p′=nki+p=n,k(i+\Delta)+p'=nki+p=n,k(i+Δ)+p′=n
于是 p′=p−kΔp'=p-k\Deltap′=p−kΔ
当 Δmax\Delta_{max}Δmax​ 时因为 p′≥0p'\ge 0p′≥0 则 Δ≤⌊pk⌋\Delta\le \lfloor\frac{p}{k}\rfloorΔ≤⌊kp​⌋ ,Δmax=⌊pk⌋\Delta_{max}= \lfloor\frac{p}{k}\rfloorΔmax​=⌊kp​⌋
求
imax′=i+Δmaxi'_{max}=i+\Delta_{max}imax′​=i+Δmax​
=i+⌊pk⌋=i+\lfloor\frac{p}{k}\rfloor=i+⌊kp​⌋
=i+⌊n−⌊ni⌋∗i⌊ni⌋⌋=i+\lfloor\frac{n-\lfloor\frac{n}{i}\rfloor*i}{\lfloor\frac{n}{i}\rfloor}\rfloor=i+⌊⌊in​⌋n−⌊in​⌋∗i​⌋
=⌊i+n−⌊ni⌋∗i⌊ni⌋⌋=\lfloor i+\frac{n-\lfloor\frac{n}{i}\rfloor*i}{\lfloor\frac{n}{i}\rfloor}\rfloor=⌊i+⌊in​⌋n−⌊in​⌋∗i​⌋
=⌊⌊ni⌋∗i+n−⌊ni⌋∗i⌊ni⌋⌋=\lfloor \frac{\lfloor\frac{n}{i}\rfloor*i+n-\lfloor\frac{n}{i}\rfloor*i}{\lfloor\frac{n}{i}\rfloor}\rfloor=⌊⌊in​⌋⌊in​⌋∗i+n−⌊in​⌋∗i​⌋
=⌊n⌊ni⌋⌋=\lfloor \frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor=⌊⌊in​⌋n​⌋
证明2：
类似于一些有关因数和分块的证明,
关于 ⌊ni⌋\lfloor\frac{n}{i}\rfloor⌊in​⌋ 的取值，我们可以这样分类

当 1≤i≤n1\le i\le \sqrt n1≤i≤n​ 时，由于 iii 最多时只有 n\sqrt nn​ 个，于是 ⌊ni⌋\lfloor\frac{n}{i}\rfloor⌊in​⌋ 最多有 n\sqrt nn​ 个 当 n<i≤n\sqrt n< i\le nn​<i≤n 时，此时 1≤⌊ni⌋<n1\le \lfloor\frac{n}{i}\rfloor< \sqrt n1≤⌊in​⌋<n​ 于是最多有 n−1\sqrt n-1n​−1 个
于是最多有 2n−12\sqrt n -12n​−1 个取值，当然一般认为有 2n2\sqrt n2n​ 个
作者：Liang-梁

数论