引理
给定正整数 (i) 和 (n) 满足 (i<=n),使得 $nover i $ = (n over x) 成立的最大的 (x) 为 (n over {n over i}).(除法为下取整)
证明
- 1.肯定存在 x 使 (n over i) = (n over x)
因为 这里的除法是向下取整,会有精度损失。
- 2. (x) 的上界为 (nover {n over i})
首先由除法的性质可得:
({n over x} imes x leq n)
然后又因为 (n over i) = (n over x), 可得:
({nover i} imes x leq n)
移项可得:
(x leq {n over {n over i}})
-3. x 的下界为 ({n over {n over i}} -1)
首先因为 (x) 是最大的满足条件的数,所以:
({nover x} < {n over {x+1}})
于是 :
({n over i} < {n over {x+1}})
移项的得 :
((x+1) imes {n over{i}} < n)
也就是:
((x+1) < {n over {nover i}})
左边剩下一个 (x) 可得
(x < {n over {n over i}} - 1)
综上 ({nover {nover i}}-1 < x leq {n over {nover i}})
所以 (x) 只能等于 (n over {n over i})