题解 - [LightOJ 1245] Harmonic Number (II)

发表于 更新于 分类于 ， 本文字数： 53 阅读时长 ≈ 1 分钟

题目链接

简述题意

求 \(\displaystyle\sum_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor\)

解题思路

数论分块模板题

代码

Show code

LightOJ_1245view raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <cstdio>
int main() {
  int kase;
  scanf("%d", &kase);
  for (int cnt = 1; cnt <= kase; ++cnt) {
    i64 n;
    scanf("%lld", &n);
    i64 ans = 0;
    for (i64 l = 1, r = 0; l <= n; l = r + 1) {
      r = n / (n / l);
      ans += (r - l + 1) * (n / l);
    }
    printf("Case %d: %lld\n", cnt, ans);
  }
  return 0;
}