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

有一道經典問題是這樣子的：
「給予一個\(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}\)