證明：連續分數取整之和的根號算法正確性

有一道經典問題是這樣子的：
「給予一個$n$，請計算$\sum\limits_{k=1}^{n}\lfloor{\frac{n}{k}}\rfloor$」

隨便寫一寫大概就會像這樣：

1 2 3 4 5 6 7 8 9 10 11

#include <bits/stdc++.h> int main() { int n,ans=0; scanf("%d",&n); for(int i=1;i<=n;i++) ans+=n/i; printf("%d\n",ans); return 0; }

可惜這樣子的時間複雜度是$O(n)$，實在太慢了。
可以發現這$n$項當中有許多項是一樣的，藉此加速便可達到$O(\sqrt{n})$。
code長這樣子：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

#include <bits/stdc++.h> int main() { int n,ans=0; scanf("%d",&n); for(int i=1;i<=n;) { int t=n/(n/i); ans+=(n/i)*(t-i+1); i=t+1; } printf("%d\n",ans); return 0; }

事實是：第9行那個動作可以精確的取到最大整數的$t$滿足$\lfloor{\frac{n}{t}}\rfloor=\lfloor{\frac{n}{i}}\rfloor$
而這篇的主旨便是要證明這件事。

證明分兩部份：

• 證明$\lfloor{\frac{n}{t}}\rfloor=\lfloor{\frac{n}{i}}\rfloor$
• 證明$t$為滿足該條件的上界，也就是證明$\lfloor{\frac{n}{t+1}}\rfloor\ne\lfloor{\frac{n}{i}}\rfloor$

首先進行第一部份的證明。
$n,m,k\in\mathbb{N^{+}}$且$\lfloor{\frac{n}{k}}\rfloor=m$，試證$\lfloor{\frac{n}{ \lfloor{\frac{n}{m}}\rfloor }}\rfloor=m$：
（$\lfloor{\frac{n}{m}}\rfloor$就相當於程式碼中的$t$、$k$相當於$i$）
1.

$\lfloor{\frac{n}{m}}\rfloor\leq\frac{n}{m}$

$m\leq\frac{n}{\lfloor{\frac{n}{m}}\rfloor}$

$m=\lfloor{m}\rfloor\leq\lfloor\frac{n}{\lfloor{\frac{n}{m}}\rfloor}\rfloor$

2.

$m=\lfloor{\frac{n}{k}}\rfloor\leq\frac{n}{k}$

$mk\leq{n}$

$k=\lfloor{k}\rfloor\leq\lfloor\frac{n}{m}\rfloor$

$\frac{n}{k}\geq\frac{n}{\lfloor\frac{n}{m}\rfloor}$

$m=\lfloor\frac{n}{k}\rfloor\geq\lfloor\frac{n}{\lfloor\frac{n}{m}\rfloor}\rfloor$

由1.、2.，得證$\lfloor{\frac{n}{ \lfloor{\frac{n}{m}}\rfloor }}\rfloor=m$

接著進行第二部份的證明。
$n,m\in\mathbb{N^{+}}$，試證$\lfloor{\frac{n}{ \lfloor{\frac{n}{m}}\rfloor +1}}\rfloor\ne{m}$：

$\frac{n}{m}<\lfloor{\frac{n}{m}}\rfloor+1$

$\frac{n}{\lfloor{\frac{n}{m}}\rfloor+1}<m$

$\lfloor\frac{n}{\lfloor{\frac{n}{m}}\rfloor+1}\rfloor\leq\frac{n}{\lfloor{\frac{n}{m}}\rfloor+1}<m$

得證$\lfloor{\frac{n}{ \lfloor{\frac{n}{m}}\rfloor +1 }}\rfloor\ne{m}$