NOIP2021 T1 某种算法复杂度的简单证明

lightup37 · 2021-11-23 15:11:26 · 个人记录

我们定义 h(x) 代表整数 x 的十进制表达下是否有至少 1 位是 7. 接下来证明 \sum\limits_{1\leq x\leq n, h(x)=1} \frac{1}{x} = \Omega(\log n).

不妨设 m 为最大的非负整数使得 10^m-1 \leq n.

有 \begin{aligned} \sum\limits_{1\leq x\leq n, h(x)=1} \frac{1}{x} &\ge \sum\limits_{1\leq x\leq 10^m-1, h(x)=1}\\&= \sum\limits_{1\leq x\leq 10^m-1} \frac{1}{x} - \sum\limits_{1\leq x\leq 10^m-1, h(x)=0} \frac{1}{x} \\&= H_{10^m-1}-\sum\limits_{1\leq t\leq m} \sum\limits_{10^{t-1}\leq x\leq 10^t-1, h(x)=0} \frac{1}{x} \\&\ge H_{10^m-1} - \sum\limits_{1\leq t\leq m}\sum\limits_{10^{t-1}\leq x\leq 10^t-1, h(x)=0} \frac{1}{10^{t-1}} \\&= H_{10^m-1} - \sum\limits_{1\leq t\leq m} 8\times9^{t-1} \frac{1}{10^{t-1}} \\&= H_{10^m-1} - 8\times \sum\limits_{0\leq t\leq m-1} (\frac{9}{10})^t \\&\ge H_{10^m-1} - 8\times 10\end{aligned}

由于 H_{10^m-1} = \Omega (\log n), 故原命题得证.

另一种简单的证明: