配点: 100 点
想看 Xmas Contest 2013 题目 G 的黑兔从远处看的白兔:「嗯嗯,f(n) 的和可以快速计算吗」
問題文
正整数 n , 定义f(n) 该值应乘以 n 是其素因数(重复计数)的个数。例如,200 = 2^3 \times 5^2 因此,f(200) = 5 变为。
正整数 N ,所以\sum_{n=1}^N f(n) 。
制約
- 1 \le N \le 10^{11}.
部分点
- N \le 10^{10} 的数据集,45 点。 如果所有满足
- 如果对于没有附加约束的数据集,除了上述之外,答案是正确的, 输出(小于 55 点。 如果所有满足
入力
N
出力
\sum_{n=1}^N f(n) 的值,直到 1 行输出。 没有
入力例 1
6
出力例 1
7
f(1) = 0,f(2) = 1,f(3) = 1,f(4) = 2,f(5) = 1,f(6) = 2 因此,答案是 0 + 1 + 1 + 2 + 1 + 2 = 7 。
入力例 2
2019
出力例 2
6028
入力例 3
906150257
出力例 3
3660251364