第 04 课 唯一分解定理
算术基本定理、约数个数与约数和
学习目标：理解唯一分解定理；掌握 \(O(\sqrt{N})\) 的质因数分解；能够利用质因数分解求正约数个数和正约数之和。
一、算术基本定理
1. 定理内容
算术基本定理，又称唯一分解定理：
每个大于 \(1\) 的自然数，要么本身是质数，要么可以唯一地写成若干个质数的乘积（不考虑顺序）。
形式化表述：对于任意正整数 \(N>1\)，存在唯一的质因数分解形式：
其中：
且 \(p_1,p_2,\dots,p_k\) 为互不相同的质数，\(a_i\) 为正整数。这种表示既存在，又唯一。
举例：
最后一个例子中，\(19\) 本身就是质数，所以它的质因数分解就是它自己。
2. 定理的两个部分
算术基本定理的内容由两部分构成：
| 部分 | 含义 | 说明 |
|---|---|---|
| 存在性 | 任意 \(N>1\) 都能分解为质数之积 | 质数是“积木”，任何大于 \(1\) 的数都能用质数拼出来。 |
| 唯一性 | 不考虑顺序时，分解方式只有一种 | 同一个数的质因数分解结果是确定的，不会有两种不同答案。 |
关键理解： “唯一”指的是质因数的种类和每个质因数的指数唯一确定，与书写顺序无关。例如 \(12=2^2\times 3\) 和 \(12=3\times 2^2\) 是同一种分解。
二、分解质因数的方法
1. 暴力枚举法
思路：\(N\) 的质因子一定在 \([2,N]\) 之间。枚举每个 \(i\)；若 \(i\) 能整除 num，就不断除以 \(i\)，直到 num 不再含因子 \(i\)，同时记录指数。
时间复杂度：\(O(N)\)。
#include <bits/stdc++.h>
using namespace std;
int main() {
int num;
cin >> num;
int factor[100] = {}, cnt[100] = {}, len = 0;
for (int i = 2; i <= num; i++) {
if (num % i == 0) {
factor[++len] = i;
while (num % i == 0) {
cnt[len]++;
num /= i;
}
}
}
for (int i = 1; i <= len; i++) {
cout << factor[i] << " " << cnt[i] << '\n';
}
return 0;
}
2. 优化法：利用 \(\sqrt{N}\) 结论
关键结论：任意正整数 \(N\) 至多有一个大于 \(\sqrt{N}\) 的质因子。
证明（反证法）：假设 \(N\) 有两个不同的质因子 \(a\)、\(b\)，且 \(a>\sqrt{N}\)、\(b>\sqrt{N}\)。
- 因为 \(a\)、\(b\) 都是 \(N\) 的质因子且互质，所以 \(ab\mid N\)，即 \(ab\le N\)。
- 但 \(a>\sqrt{N}\)、\(b>\sqrt{N}\)，所以：
- 两条结论矛盾。因此，\(N\) 不可能有两个都大于 \(\sqrt{N}\) 的质因子，至多只有一个。
推论：枚举到 \(\sqrt{N}\) 就够了。若循环结束后
num > 1，剩下的num就是那个唯一大于 \(\sqrt{N}\) 的质因子。
时间复杂度：\(O(\sqrt{N})\)。
#include <bits/stdc++.h>
using namespace std;
int main() {
int num;
cin >> num;
int factor[100] = {}, cnt[100] = {}, len = 0;
for (int i = 2; i <= num / i; i++) {
if (num % i == 0) {
factor[++len] = i;
while (num % i == 0) {
cnt[len]++;
num /= i;
}
}
}
if (num > 1) {
factor[++len] = num;
cnt[len] = 1;
}
for (int i = 1; i <= len; i++) {
cout << factor[i] << " " << cnt[i] << '\n';
}
return 0;
}
3. 两种方法对比
| 对比项 | 暴力枚举法 | 优化法 |
|---|---|---|
| 枚举范围 | \([2,N]\) | \([2,\sqrt{N}]\) |
| 时间复杂度 | \(O(N)\) | \(O(\sqrt{N})\) |
| 循环条件 | i <= num |
i <= num / i |
| 收尾处理 | 不需要 | 需要判断 num > 1 |
| 适用场景 | 理解原理 | 实际比赛必用 |
易错点：循环条件写成
i * i <= num也能用，但当 \(N\) 接近int上限时，i * i可能溢出。使用i <= num / i更安全。
三、约数个数定理
1. 定理内容
由算术基本定理，正整数 \(N>1\) 分解为：
则 \(N\) 的正约数个数为：
2. 证明
对于第 \(i\) 个质因子 \(p_i^{a_i}\)，它的正约数有：
共 \(a_i+1\) 个。
\(N\) 的任意一个约数，都可以从每个质因子的幂中选择一个：
- \(p_1\) 的指数可以从 \(0\) 到 \(a_1\) 中选择；
- \(p_2\) 的指数可以从 \(0\) 到 \(a_2\) 中选择；
- 以此类推。
各个质因子的选择互相独立，因此根据乘法原理，约数总数为：
一句话理解：每个质因子的指数从 \(0\) 取到 \(a_i\)，有 \(a_i+1\) 种取法；各质因子的取法相乘，就是约数总数。
3. 举例
例 1： \(60=2^2\times 3^1\times 5^1\)。
三个质因子的指数分别是 \(2,1,1\)，所以：
\(60\) 的 12 个正约数为：
例 2： \(360=2^3\times 3^2\times 5^1\)。
4. 代码实现
#include <bits/stdc++.h>
using namespace std;
int main() {
int num;
cin >> num;
long long ans = 1;
for (int i = 2; i <= num / i; i++) {
if (num % i == 0) {
int cnt = 0;
while (num % i == 0) {
cnt++;
num /= i;
}
ans *= (cnt + 1);
}
}
if (num > 1) {
ans *= 2;
}
cout << ans << '\n';
return 0;
}
关键代码说明：
| 代码 | 作用 |
|---|---|
long long ans = 1; |
答案初始化为 \(1\)，因为 \(1\) 是乘法的单位元。 |
int cnt = 0; |
统计当前质因子的指数。 |
ans *= (cnt + 1); |
套用公式：当前质因子贡献“指数 \(+1\)”。 |
if (num > 1) ans *= 2; |
剩余质因子的指数为 \(1\)，贡献 \(1+1=2\)。 |
四、约数和定理
1. 定理内容
由算术基本定理，正整数 \(N>1\) 分解为：
则 \(N\) 的所有正约数之和为：
展开写为：
2. 证明
第一步：计算单个质因子的贡献
对于第 \(i\) 个质因子 \(p_i^{a_i}\)，它的幂约数为：
这一组约数之和记为 \(S_i\)：
这是一个首项为 \(1\)、公比为 \(p_i\)、项数为 \(a_i+1\) 的等比数列。
第二步：利用等比数列求和公式
记：
两边同乘以 \(p_i\)：
用（2）式减去（1）式：
所以：
第三步：组合所有质因子的选择
\(N\) 的每个正约数，都可以从每个质因子的幂约数中各选一个并相乘得到。根据乘法原理，所有约数的和就是各组约数和的乘积：
一句话理解：每个质因子贡献一组约数和 \(S_i\)；各组取法按乘法原理组合，所以总约数和等于各组约数和之积。
3. 举例
例 1： \(60=2^2\times3^1\times5^1\)。
验证：
例 2： \(12=2^2\times3^1\)。
验证：
4. 代码实现
#include <bits/stdc++.h>
using namespace std;
int main() {
int num;
cin >> num;
long long ans = 1;
for (int i = 2; i <= num / i; i++) {
if (num % i == 0) {
int cnt = 0;
while (num % i == 0) {
cnt++;
num /= i;
}
// 计算 p^0 + p^1 + ... + p^cnt
// 直接累加，避免使用除法
long long sum = 0;
long long pk = 1;
for (int j = 0; j <= cnt; j++) {
sum += pk;
pk *= i;
}
ans *= sum;
}
}
if (num > 1) {
ans *= (1 + num);
}
cout << ans << '\n';
return 0;
}
注意：约数和可能很大，
ans必须使用long long。上面代码直接累加 \(p^0+p^1+\dots+p^a\)，避免了公式中的除法，计算更稳妥。
五、三个定理的关系
| 定理 | 作用 | 公式 |
|---|---|---|
| 唯一分解定理 | 把 \(N\) 拆成质数之积 | \(N=\prod p_i^{a_i}\) |
| 约数个数定理 | 求 \(N\) 有多少个约数 | \(d(N)=\prod(a_i+1)\) |
| 约数和定理 | 求 \(N\) 所有约数之和 | \(S(N)=\prod\frac{p_i^{a_i+1}-1}{p_i-1}\) |
逻辑链条：唯一分解定理是“根”。先得到 \(N=\prod p_i^{a_i}\)，才能继续套公式求约数个数和约数和。
六、常见错误与注意事项
| 编号 | 错误 | 后果 | 改正 |
|---|---|---|---|
| E1 | 循环条件写成 i * i <= num |
\(N\) 接近 int 上限时 i*i 溢出 |
写成 i <= num / i |
| E2 | 忘记处理 num > 1 的剩余质因子 |
漏掉最大的质因子 | 循环后判断 if (num > 1) |
| E3 | 约数和使用 int 存储 |
结果溢出，答案错误 | 使用 long long |
| E4 | 约数个数公式写成 \(\prod a_i\) | 漏掉 \(+1\) | 公式应为 \(\prod(a_i+1)\) |
| E5 | 把 \(1\) 当成质数 | 分解结果多一个因子 | \(1\) 既不是质数也不是合数 |
| E6 | 列举约数时把非约数算进去 | 验证不通过 | 逐个检查 \(N\) 能否被 \(d\) 整除 |
| E7 | 分解时没有把质因子除干净 | 指数统计错误 | 使用 while 连续除，不是 if |
重点记忆：循环到 \(\sqrt{N}\) 后，不要忘记处理剩余的
num > 1；求约数和时使用long long；分解同一个质因子时必须用while除干净。
七、方法、套路与策略小结
1. 分解质因数的套路
- 定范围：枚举范围是 \([2,\sqrt{N}]\)，不是 \([2,N]\)。
- 除干净：每个质因子都用
while循环除到不能整除为止，并统计指数。 - 查剩余：循环结束后若
num > 1，剩下的就是那个唯一大于 \(\sqrt{N}\) 的质因子。 - 防溢出：循环条件用
i <= num / i，不用i * i <= num。
2. 求约数个数和约数和的套路
- 先分解：先做质因数分解，得到每个 \(p_i\) 和 \(a_i\)。
- 套公式：约数个数套 \(\prod(a_i+1)\)；约数和套 \(\prod\frac{p_i^{a_i+1}-1}{p_i-1}\)。
- 防溢出：约数和用
long long，中间结果同样关注数据范围。 - 收尾处理：不要忘记
if (num > 1)的剩余质因子，它的指数为 \(1\)。
3. 信奥策略意识
- 复杂度意识：\(O(\sqrt{N})\) 的分解是数论题的基础工具。\(N\le 10^{12}\) 时，\(\sqrt{N}\le 10^6\)。
- 数据范围意识：约数个数和约数和都可能很大；必要时使用
long long或按题意取模。 - 验证习惯：小数据可以列举约数验证个数，也可以直接求和验证约数和。
- 公式记忆：先记住分解形式 \(N=\prod p_i^{a_i}\)，其余两个公式都能从“指数选择”和“等比数列求和”推出来。