AtCoder Beginner Contest 230 E 問題 Fraction Floor Sum

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$\displaystyle \sum_{i=1}^N \left \lfloor \dfrac{N}{i} \right \rfloor$ を求めよ.

制約

$1 \leq N \leq 10^{12}$

解法

この問題は, 以下の事実が本質的である.

$\# \left\{\left \lfloor \dfrac{N}{i} \right \rfloor \middle| 1 \leq i \leq N, i \in \mathbb{Z} \right\}=O(\sqrt{N})$

証明
$K=\lceil \sqrt{N} \rceil$ とする. このとき, $i \geq K$ ならば, $\displaystyle \left \lfloor \dfrac{N}{i} \right \rfloor \leq K$ である. よって,

$\begin{align} &\phantom{=} \# \left\{\left \lfloor \dfrac{N}{i} \right \rfloor \middle| 1 \leq i \leq N, i \in \mathbb{Z} \right\} \\\\ &=\# \left(\left\{\left \lfloor \dfrac{N}{i} \right \rfloor \middle| 1 \leq i \lt K, i \in \mathbb{Z} \right\} \cup \left\{\left \lfloor \dfrac{N}{i} \right \rfloor \middle| K \leq i \leq N, i \in \mathbb{Z} \right\} \right) \\\\ &\leq \# \left\{\left \lfloor \dfrac{N}{i} \right \rfloor \middle| 1 \leq i \lt K, i \in \mathbb{Z} \right\}+\# \left\{\left \lfloor \dfrac{N}{i} \right \rfloor \middle| K \leq i \leq N, i \in \mathbb{Z} \right\} \\\\ &\leq \# \left\{\left \lfloor \dfrac{N}{1} \right \rfloor, \dots, \left \lfloor \dfrac{N}{K} \right \rfloor \right\}+\# \{1,2, \dots, K\}\\\\ &=K+K \\\\ &=2K \\\\ &=2 \lceil \sqrt{N} \rceil \\\\ &=O(\sqrt{N}) \end{align}$