「模板」整除分块
背景
- Idea: 模板题
- Data: oistream
- Solution: oistream
- 题面: oistream
描述
给定正整数 \(n\),求
\[\sum_{i=1}^{n}{\lfloor\dfrac{n}{i}\rfloor}\]
输入格式
一个整数 \(n\)。
输出格式
一个整数,即所求。
样例
样例输入1
10
样例输出1
27
样例解释
\(\sum_{i=1}^{10}{\lfloor\dfrac{10}{i}\rfloor}=\lfloor\dfrac{10}{1}\rfloor+\lfloor\dfrac{10}{2}\rfloor+\lfloor\dfrac{10}{3}\rfloor+\lfloor\dfrac{10}{4}\rfloor+\lfloor\dfrac{10}{5}\rfloor+\lfloor\dfrac{10}{6}\rfloor+\lfloor\dfrac{10}{7}\rfloor+\lfloor\dfrac{10}{8}\rfloor+\lfloor\dfrac{10}{9}\rfloor+\lfloor\dfrac{10}{10}\rfloor=10+5+3+2+2+1+1+1+1+1=27\)。
数据规模与约定
对于 \(60\%\) 的数据,\(1\leq n\leq 10^8\)。
对于全部数据,\(1\leq n\leq 10^9\)。
时间限制 \(1\text{ s}\),空间限制 \(256\text{ MB}\)。