[AHOI2005] 约数研究

题意

求 1..n 每个整数约数个数的总和。

思路

约数 d 会成为 d,2d,... 共 floor(n/d) 个数的约数，因此交换统计顺序：

\sum_{i=1}^n f(i)=\sum_{d=1}^n\left\lfloor\frac nd\right\rfloor

还可以利用整除分块。对于当前 left，商 q=n//left 在连续区间 [left,n//q] 内不变，整段贡献为 q*(right-left+1)，然后跳到下一段。

Python 知识

// 是整数向下除法，直接对应公式中的下取整。
divmod 不需要用于这里，因为商相同区间右端可由 n//quotient 得到。
Python 大整数安全累加约数总数。
while left<=n 按块跳跃，循环次数约为 2*sqrt(n)。
/home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md：整数除法和任意精度。
/home/rainboy/mycode/hugo-blog/content/program_language/python/generator_expression.md：从逐项求和到按块归并。

代码

python

1
2
3
4
5
6
7
8
9
10
11n = int(input())
answer = 0
left = 1

while left <= n:
    quotient = n // left
    right = n // quotient
    answer += quotient * (right - left + 1)
    left = right + 1

print(answer)

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26/**
 * P1403 [AHOI2005] 约数研究
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    long long ans = 0;
    // 1~n 中，约数 d 出现 ⌊n/d⌋ 次
    // 对 ⌊n/d⌋ 相等的 d 合并计算
    for (int l = 1, r; l <= n; l = r + 1) {
        int q = n / l;
        r = n / q;
        ans += 1LL * q * (r - l + 1);
    }
    printf("%lld\n", ans);
    return 0;
}

复杂度

整除分块时间复杂度 $O(\sqrt n)$ ，额外空间 $O(1)$ 。

总结

从“每个数有多少约数”切换为“每个约数出现多少次”得到调和和，再按相同商分块可继续加速。

[AHOI2005] 约数研究

目录

题意

思路

Python 知识

代码

复杂度

总结