/ 7FOJ / 题库 /

「模板」整除分块

「模板」整除分块

背景

  • 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}\)。

信息

ID
1100
难度
5
分类
分块数论 点击显示
标签
递交数
4
已通过
2
通过率
50%
被复制
1
上传者