目录
编辑
前言
一、约数的核心概念与性质
[1.1 约数的定义](#1.1 约数的定义)
[1.2 约数的核心性质](#1.2 约数的核心性质)
二、求单个整数的所有约数：试除法的优化与实现
[2.1 试除法的核心思路](#2.1 试除法的核心思路)
[2.2 避免重复与溢出的技巧](#2.2 避免重复与溢出的技巧)
[2.3 C++ 实现求单个整数的所有约数](#2.3 C++ 实现求单个整数的所有约数)
[2.4 代码测试与分析](#2.4 代码测试与分析)
三、求区间内所有数的约数集合：倍数法的高效应用
[3.1 试除法的局限性](#3.1 试除法的局限性)
[3.2 倍数法的核心思路](#3.2 倍数法的核心思路)
[3.3 C++ 实现区间内所有数的约数集合](#3.3 C++ 实现区间内所有数的约数集合)
[3.4 时间复杂度分析](#3.4 时间复杂度分析)
四、约数个数定理与约数和定理：公式法的应用
[4.1 约数个数定理](#4.1 约数个数定理)
[4.2 约数和定理](#4.2 约数和定理)
[4.3 公式法求约数个数与约数和](#4.3 公式法求约数个数与约数和)
[4.4 C++ 实现公式法求约数个数与约数和](#4.4 C++ 实现公式法求约数个数与约数和)
[4.5 代码测试与优化](#4.5 代码测试与优化)
[五、实战例题 1：牛客网 约数之和](#五、实战例题 1：牛客网 约数之和)
[5.1 题目分析](#5.1 题目分析)
[5.2 试除法解法实现](#5.2 试除法解法实现)
[5.3 代码分析](#5.3 代码分析)
[六、实战例题 2：牛客网 约数个数的和](#六、实战例题 2：牛客网 约数个数的和)
[6.1 题目分析](#6.1 题目分析)
[6.2 优化思路：反向统计约数个数](#6.2 优化思路：反向统计约数个数)
[6.3 高效解法实现](#6.3 高效解法实现)
[6.4 代码分析](#6.4 代码分析)
七、进阶优化：数论分块优化约数个数和
[7.1 数论分块的核心思想](#7.1 数论分块的核心思想)
[7.2 数论分块的区间计算](#7.2 数论分块的区间计算)
[7.3 C++ 实现数论分块优化约数个数和](#7.3 C++ 实现数论分块优化约数个数和)
[7.4 时间复杂度分析](#7.4 时间复杂度分析)
八、常见误区与避坑指南
[8.1 数值溢出问题](#8.1 数值溢出问题)
[8.2 边界条件处理](#8.2 边界条件处理)
[8.3 效率优化误区](#8.3 效率优化误区)
总结
前言
在算法竞赛的数论板块中，约数相关问题是仅次于质数的高频考点。无论是求一个数的所有约数，还是计算约数个数、约数和，亦或是统计区间内所有数的约数集合，这些问题看似独立，实则都围绕着约数的核心性质展开。本文将从约数的基本概念出发，层层拆解各类约数问题的求解思路，带你彻底掌握约数相关问题的解题技巧，让你在竞赛中轻松应对各类约数挑战。下面就让我们正式开始吧！
一、约数的核心概念与性质
1.1 约数的定义
约数（又称因数）是指整数 a 除以整数 b（b≠0）除得的商正好是整数而没有余数，此时称 b 是 a 的约数，记作 b|a。例如，12 的约数有 1、2、3、4、6、12，因为这些数都能整除 12 且没有余数。
特别注意：
1 是所有正整数的约数；
一个数的最大约数是它本身，最小约数是 1；
约数具有成对出现的性质：如果 d 是 a 的约数，那么 a/d 也一定是 a 的约数。例如 12 的约数中，2 和 6 成对，3 和 4 成对，1 和 12 成对。
1.2 约数的核心性质
约数的成对出现性质是解决各类约数问题的关键，它能将约数的枚举范围从 1, a 缩小到 1, √a，极大地提升算法效率。例如，要找出 100 的所有约数，只需枚举 1 到 10（√100=10），当找到一个约数 i 时，即可同时得到另一个约数 100/i。
此外，约数还具有以下性质：
若 d 是 a 和 b 的约数，则 d 也是**gcd (a, b)**的约数；
若 a 是 b 的倍数，则 b 的所有约数也都是 a 的约数（前提是 a 能被 b 整除）。
这些性质看似简单，却是后续优化算法的重要依据，在解决复杂约数问题时能起到事半功倍的效果。
二、求单个整数的所有约数：试除法的优化与实现
2.1 试除法的核心思路
根据约数成对出现的性质，求单个整数 x 的所有约数时，只需枚举 1, √x 范围内的所有整数 i：
若 i 能整除 x，则 i 是 x 的约数，同时 x/i 也是 x 的约数；
若 i = x/i（即 x 是完全平方数），则只需记录一次（避免重复）。
举个例子，求 36 的所有约数：
√36=6，枚举 1 到 6 的整数；
i=1：36%1==0，记录 1 和 36；
i=2：36%2==0，记录 2 和 18；
i=3：36%3==0，记录 3 和 12；
i=4：36%4==0，记录 4 和 9；
i=5：36%5!=0，跳过；
i=6：36%6==0，6=36/6，记录 6；
最终约数集合：{1, 2, 3, 4, 6, 9, 12, 18, 36}。
2.2 避免重复与溢出的技巧
在代码实现中，需要注意两个关键问题：
重复记录：当 x 是完全平方数时，i 和 x/i 相等，此时只需记录一次；
数值溢出 ：枚举条件若写成i*i <= x，当 x 接近 1e12 时，i*i 可能超出 int 范围，因此推荐使用i <= x / i的写法，既避免溢出，又无需调用 sqrt 函数（减少精度误差）。
2.3 C++ 实现求单个整数的所有约数
cpp
复制代码
#include
#include
#include
using namespace std;
// 求x的所有约数，返回有序列表
vector
vector
// 枚举到sqrt(x)
for (int i = 1; i <= x / i; ++i) {
if (x % i == 0) {
res.push_back(i);
// 避免重复记录完全平方数的约数
if (i != x / i) {
res.push_back(x / i);
}
}
}
// 排序，使输出更规范
sort(res.begin(), res.end());
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int x;
cin >> x;
auto divisors = get_divisors(x);
cout << x << "的约数有：";
for (int d : divisors) {
cout << d << " ";
}
cout << endl;
return 0;
}
2.4 代码测试与分析
输入：36
输出：36 的约数有：1 2 3 4 6 9 12 18 36
时间复杂度 ：O (√x)。枚举范围从 x 缩小到√x，效率大幅提升。对于 x=1e12，√x=1e6，仅需枚举 1e6 次，完全可以在毫秒级完成。
空间复杂度 ：O (τ(x))，其中 τ(x) 是 x 的约数个数（约数函数）。一个数的约数个数上限为 2√x（如 x=1e6 时，约数个数最多为 100），空间开销可忽略。
三、求区间内所有数的约数集合：倍数法的高效应用
3.1 试除法的局限性
当需要求 1, n 范围内所有数的约数集合时，若对每个数单独使用试除法，时间复杂度为 O (n√n)。对于 n=1e5，n√n≈1e7.5，虽然能通过，但效率较低；对于 n=1e6，n√n≈1e9，会直接超时。
此时需要一种更高效的方法 ------ 倍数法 ，利用 "约数的倍数" 这一反向思维，将时间复杂度优化至 O (n log n)。
3.2 倍数法的核心思路
倍数法的本质是**"反向枚举约数"**：对于每个约数 d，1, n 中所有以 d 为约数的数都是 d 的倍数（即 d, 2d, 3d, ..., kd，其中 kd ≤n）。因此，我们可以：
枚举每个可能的约数 d（从 1 到 n）；
枚举 d 的所有倍数 m（d, 2d, ..., kd ≤n）；
将 d 添加到 m 的约数集合中。
举个例子，求 1, 6 范围内所有数的约数集合：
d=1：倍数为 1,2,3,4,5,6 → 给每个数的约数集合添加 1；
d=2：倍数为 2,4,6 → 给 2,4,6 的约数集合添加 2；
d=3：倍数为 3,6 → 给 3,6 的约数集合添加 3；
d=4：倍数为 4 → 给 4 的约数集合添加 4；
d=5：倍数为 5 → 给 5 的约数集合添加 5；
d=6：倍数为 6 → 给 6 的约数集合添加 6；
最终结果：1：{1}2：{1,2}3：{1,3}4：{1,2,4}5：{1,5}6：{1,2,3,6}
3.3 C++ 实现区间内所有数的约数集合
cpp
复制代码
#include
#include
using namespace std;
const int MAXN = 1e5 + 10;
vector
// 预处理[1, n]范围内所有数的约数集合
void pre_divisors(int n) {
// 枚举每个约数d
for (int d = 1; d <= n; ++d) {
// 枚举d的所有倍数m
for (int m = d; m <= n; m += d) {
divisors[m].push_back(d);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
pre_divisors(n);
// 输出每个数的约数集合
for (int m = 1; m <= n; ++m) {
cout << m << "的约数：";
for (int d : divisors[m]) {
cout << d << " ";
}
cout << endl;
}
return 0;
}
3.4 时间复杂度分析
倍数法的时间复杂度为 O (n log n)，这是因为：
对于约数 d，其倍数个数为 n/d；
总操作次数为 n/1 + n/2 + n/3 + ... + n/n = n (1 + 1/2 + 1/3 + ... + 1/n)；
括号内的部分是调和级数 ，当 n 较大时，调和级数的和约为log n + γ（γ 为欧拉常数，约 0.577），因此总时间复杂度为 O (n log n)。
对于 n=1e6，n log n≈1e6×20=2e7，完全可以在 1 秒内完成预处理，效率远高于试除法。
四、约数个数定理与约数和定理：公式法的应用
4.1 约数个数定理
由算术基本定理，任何大于 1 的自然数 n 都可以唯一分解为质因数的乘积：
其中 p₁ 约数个数定理指出：n 的约数个数为所有质因子指数加 1 后的乘积，即： 原理：每个质因子 pᵢ可以选择 0 到 αᵢ个，共 (αᵢ+1) 种选择，所有质因子的选择组合即为约数的总数。 示例：n=12=2²×3¹，约数个数为 (2+1)×(1+1)=6，分别是 1 (2⁰×3⁰)、2 (2¹×3⁰)、3 (2⁰×3¹)、4 (2²×3⁰)、6 (2¹×3¹)、12 (2²×3¹)。 4.2 约数和定理 约数和定理指出：n 的所有约数之和为每个质因子的幂次和的乘积，即： 原理：将每个质因子的所有可能次幂相加，再将结果相乘，得到所有约数的和（乘法分配律）。 示例：n=12=2²×3¹，约数和为 (1+2+4)×(1+3)=7×4=28，验证：1+2+3+4+6+12=28。 4.3 公式法求约数个数与约数和 结合质因数分解，我们可以通过公式法快速计算约数个数和约数和，步骤如下： 对 n 进行质因数分解，得到标准分解式； 根据约数个数定理计算约数个数； 根据约数和定理计算约数和。 4.4 C++ 实现公式法求约数个数与约数和 cpp 复制代码 #include #include using namespace std; // 质因数分解，返回质因子及其指数 unordered_map unordered_map for (int i = 2; i <= x / i; ++i) { while (x % i == 0) { factors[i]++; x /= i; } } if (x > 1) { factors[x] = 1; } return factors; } // 计算约数个数 int count_divisors(int x) { if (x == 1) return 1; auto factors = prime_factor(x); int res = 1; for (auto [p, alpha] : factors) { res *= (alpha + 1); } return res; } // 计算约数和 long long sum_divisors(int x) { if (x == 1) return 1; auto factors = prime_factor(x); long long res = 1; for (auto [p, alpha] : factors) { long long s = 1; long long pow_p = 1; // 计算1 + p + p^2 + ... + p^alpha for (int i = 1; i <= alpha; ++i) { pow_p *= p; s += pow_p; } res *= s; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; cout << n << "的约数个数：" << count_divisors(n) << endl; cout << n << "的约数和：" << sum_divisors(n) << endl; return 0; } 4.5 代码测试与优化 输入：12 输出：12 的约数个数：612 的约数和：28 优化点： 约数和计算中，使用long long 存储结果，避免溢出（如 n=1e5 时，约数和可能超过 int 范围）； 质因数分解时，同样使用i <= x / i的枚举条件，避免溢出。 五、实战例题 1：牛客网 约数之和 题目链接：https://ac.nowcoder.com/acm/problem/22196 5.1 题目分析 题目描述：求自然数 N 的所有约数之和（N≤1e4）。 输入：一行一个正整数 N。 输出：一行一个整数，表示 N 的约数和。 示例：输入：10 输出：18（1+2+5+10=18）。 解题思路：本题可使用试除法或公式法求解。由于 N≤1e4，两种方法效率差异不大，试除法实现更简洁。 5.2 试除法解法实现 cpp 复制代码 #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; long long sum = 0; for (int i = 1; i <= n / i; ++i) { if (n % i == 0) { sum += i; if (i != n / i) { sum += n / i; } } } cout << sum << endl; return 0; } 5.3 代码分析 时间复杂度 ：O (√n)，对于 n=1e4，√n=100，仅需枚举 100 次； 空间复杂度 ：O (1)，无需额外存储约数集合，直接累加求和； 输入输出优化 ：使用ios::sync_with_stdio(false); **cin.tie(nullptr);**提升读取速度。 六、实战例题 2：牛客网 约数个数的和 题目链接：https://ac.nowcoder.com/acm/problem/14682 6.1 题目分析 题目描述：给定 n，求 1 到 n 的所有数的约数个数的和（n≤1e6）。 输入：一行一个正整数 n。 输出：一行一个整数，表示答案。 示例：输入：3 输出：5（1 的约数个数 1 + 2 的约数个数 2 + 3 的约数个数 2 = 5）。 核心难点：若对每个数单独计算约数个数，时间复杂度为 O (n√n)，n=1e6 时会超时。需利用倍数法的反向思维优化。 6.2 优化思路：反向统计约数个数 根据倍数法的思想，对于每个约数 d，1, n 中以 d 为约数的数有 n/d 个（即 d 的倍数个数）。因此，1 到 n 的约数个数的和等于所有 d 从 1 到 n 的 n/d 之和。 示例：n=3 d=1：倍数有 1,2,3 → 贡献 3； d=2：倍数有 2 → 贡献 1； d=3：倍数有 3 → 贡献 1； 总和：3+1+1=5，与示例一致。 6.3 高效解法实现 cpp 复制代码 #include using namespace std; typedef long long LL; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; LL sum = 0; // 枚举每个约数d，贡献为n/d for (int d = 1; d <= n; ++d) { sum += n / d; } cout << sum << endl; return 0; } 6.4 代码分析 时间复杂度 ：O (n)，对于 n=1e6，仅需循环 1e6 次，完全可以在 1 秒内完成； 空间复杂度 ：O (1)，仅需一个变量存储总和； 关键优化：将 "求每个数的约数个数" 转化为 "统计每个约数的倍数个数"，从 O (n√n) 优化到 O (n)，效率大幅提升。 七、进阶优化：数论分块优化约数个数和 7.1 数论分块的核心思想 对于 n=1e7，O (n) 的时间复杂度可能会超时（1e7 次循环约需 1 秒）。此时可以使用数论分块（又称整除分块）进一步优化，将时间复杂度降至 O (√n)。 数论分块的核心观察：对于连续的区间 l, r，n/d 的值可能相同。例如 n=10： d=1→10/1=10； d=2→10/2=5； d=3→10/3=3； d=4→10/4=2； d=5→10/5=2； d=6→10/6=1； d=7→10/7=1； d=8→10/8=1； d=9→10/9=1； d=10→10/10=1； 可以发现，n/d 的值相同的区间为 1,1、2,2、3,3、4,5、6,10。对于每个区间 l, r，n/d 的值为 k，贡献为 k*(r-l+1)。 7.2 数论分块的区间计算 对于当前 l，r 的计算方式为：r = n / (n /l)。例如 n=10，l=4 时，n/l=2，r=10/2=5，即区间 4,5。 7.3 C++ 实现数论分块优化约数个数和 cpp 复制代码 #include using namespace std; typedef long long LL; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; LL sum = 0; // 数论分块，l和r为当前区间的左右端点 for (int l = 1, r; l <= n; l = r + 1) { r = n / (n / l); sum += (LL)(n / l) * (r - l + 1); } cout << sum << endl; return 0; } 7.4 时间复杂度分析 数论分块的时间复杂度为O (√n)，因为 n/d 的不同取值最多有 2√n 种（当 d≤√n 时，n/d 有√n 种取值；当 d>√n 时，n/d<√n，也有√n 种取值）。对于 n=1e12，√n=1e6，仅需循环 1e6 次，效率极高。 八、常见误区与避坑指南 8.1 数值溢出问题 约数和计算时，未使用 long long 导致溢出（如 n=1e5 时，约数和可能达到 1e10）； 数论分块中，(n/l)*(r-l+1) 未强制转换为long long（n=1e6 时，n/l=1e6，r-l+1=1e6，乘积为 1e12，超出 int 范围）。 8.2 边界条件处理 忽略 n=1 的情况（1 的约数个数为 1，约数和为 1）； 完全平方数的约数重复记录（如 x=4，i=2 时，i=x/i，需只记录一次）； 倍数法中，枚举约数 d 时从 0 开始（d=0 不是任何数的约数，应从 1 开始）。 8.3 效率优化误区 对区间约数集合使用试除法（n=1e6 时超时）； 约数个数和计算时未使用数论分块（n=1e7 时超时）； 质因数分解时使用i*i <= x导致溢出（应使用i <= x / i）。 总结 除了掌握本文介绍的基础方法，还需要多做综合性题目，加深对约数性质的理解，提升知识的融会贯通能力。 如果你在学习过程中遇到具体题目无法解决，或者想进一步了解约数与其他数论知识的结合应用，可以随时留言交流。后续将持续更新数论进阶内容，敬请关注！