#JXGQ22002. 强哥的“约饭”计划
强哥的“约饭”计划
强哥最近决定用数学方法来制定他的“约饭”计划。他想知道,从1号到第$n$号,每一天他可以“约饭”成功的可能性有多少次。
强哥定义一个“约饭”成功的条件:
如果第$i$号能整除第$j$号(即$j % i = 0$),那么强哥可以认为第$j$号这一天能够和第$i$号成功“约饭”。例如,第8号可以成功和第1号、第2号、第4号和第8号“约饭”,因为这些数都是8的约数。
现在,强哥想知道,从第1号到第$n$号,总共能成功“约饭”的次数是多少?
输入格式:
一个整数 $n$,表示总共有 $n$ 天。
输出格式:
一个整数,表示总共能成功“约饭”的次数。
输入输出样例:
样例 1:
5
输出 1:
10
样例解释:
对于输入 5
,表示从第1号到第5号,共有5天。我们需要计算每一天能够成功“约饭”的次数,然后将这些次数相加。
具体计算如下:
- 第1号:1的约数是1,所以第1号可以和自己“约饭”,成功次数为1。
- 第2号:2的约数是1和2,所以第2号可以和第1号、第2号“约饭”,成功次数为2。
- 第3号:3的约数是1和3,所以第3号可以和第1号、第3号“约饭”,成功次数为2。
- 第4号:4的约数是1、2、4,所以第4号可以和第1号、第2号、第4号“约饭”,成功次数为3。
- 第5号:5的约数是1和5,所以第5号可以和第1号、第5号“约饭”,成功次数为2。
将这些成功次数相加:1 + 2 + 2 + 3 + 2 = 10。
因此,输出为 10
。
数据范围与约定:
- 对于 $10%$ 的数据,$1 \le n \le 10^2$
- 对于 $50%$ 的数据,$1 \le n \le 10^5$
- 对于 $100%$ 的数据,$1 \le n \le 10^7$