竞极 Ace

5 唯一分解定理

GESP C++ 五级：唯一分解定理精讲

核心目标：掌握唯一分解定理（算术基本定理）的原理与应用，熟练编写质因数分解代码，掌握约数个数定理、约数和定理，能运用唯一分解定理解决最大公约数/最小公倍数、完全平方数判断、质因子统计等综合问题。
任何大于1的整数都能唯一地分解为质数的乘积；分解靠试除法从2枚举到√n，约数个数用“指数+1连乘”，约数和用“等比数列求和连乘”。

一、考纲定位

根据CCF官方考纲，五级知识内容明确要求：“掌握辗转相除法（也称欧几里得算法）、素数表的埃氏筛法和线性筛法、唯一分解定理的原理和应用”。考核目标进一步指出：“掌握初等数论知识点，能够使用辗转相除法、素数表的埃氏筛法和线性筛法、唯一分解定理等相关知识解决相应的问题”。

在GESP五级考试中，数论是最高频考点，累计出现8道真题，其中质因数分解（唯一分解定理）出现频率最高。B3871《因数分解》考了3次，是五级数论中最核心的题型。

二、唯一分解定理

1. 定理的严格表述

任何一个大于1的正整数 n，都可以唯一地表示成有限个质数的乘积形式：

n=p1k1×p2k2×...×pmkmn = p₁^{k¹} × p₂^{k²} × ... × pₘ^{kᵐ}

其中 p₁ < p₂ < ... < pₘ 是质数，k₁, k₂, ..., kₘ 是正整数，且这种分解方式在不考虑顺序的情况下是唯一的。

这个表达式称为 n 的标准分解式。

2. 定理的两个部分

部分 含义 说明
存在性 任何大于1的整数都可以分解为质数乘积 保证分解一定能做到
唯一性 分解结果是唯一的（不计顺序） 保证分解结果是确定的

注意：唯一分解定理并未直接给出“如何判断一个数是否为质数” ，它保证的是分解的存在性和唯一性。

3. 定理的意义

唯一分解定理将复杂的乘除运算转化为直观的指数操作，简化了最大公约数和最小公倍数的计算过程，也是证明 √2 是无理数等数学命题的基础。

高频选择题（2024年3月五级第1题）：

唯一分解定理描述的内容是（ ）？
A. 任意整数都可以分解为素数的乘积
B. 每个合数都可以唯一分解为一系列素数的乘积
C. 两个不同的整数可以分解为相同的素数乘积
D. 以上都不对
答案：B
解析：任何一个大于1的整数n都可以分解成若干个素因数的连乘积。A错误，因为0、1和负数不适用；C错误，两个不同的整数不可能分解为完全相同的素数乘积。

三、质因数分解的代码实现（试除法）

1. 核心思想

试除法：从最小的质数2开始，依次尝试能否整除 n。如果能整除，就一直除到不能整除为止，同时记录该质因数的指数。枚举到 √n 即可停止。

关键性质：n 中最多只包含一个大于 √n 的质因子。如果有两个，它们乘起来就 > n 了。

2. 标准代码模板

void factorize(int n) {
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) {
                n /= i;
                cnt++;
            }
            cout << i << "^" << cnt << endl;   // 输出底数和指数
        }
    }
    if (n > 1) {
        cout << n << "^1" << endl;   // 最后剩下的大于√n的质因子
    }
}

代码要点：

要点 说明
i * i <= n 枚举到 √n，不是枚举到 n
while (n % i == 0) 反复除，直到不能整除，同时统计指数
n /= i 每次除以质因子，n 不断缩小
if (n > 1) 处理最后剩下的大于 √n 的质因子

3. 执行示例

以 n = 360 为例：

360 ÷ 2 = 180  cnt=1
180 ÷ 2 = 90   cnt=2
90  ÷ 2 = 45   cnt=3
45  ÷ 2 不能整除 → 输出 2^3
45  ÷ 3 = 15   cnt=1
15  ÷ 3 = 5    cnt=2
5   ÷ 3 不能整除 → 输出 3^2
i=4, 4*4=16 > 5，循环结束
n=5 > 1 → 输出 5^1

结果：360 = 2^3 × 3^2 × 5

4. 复杂度分析

试除法的时间复杂度为 O(√n)。对于 n ≤ 10⁹ 的数据范围完全够用。对于更大的数（如 n ≤ 10¹⁸），需要配合 Miller-Rabin（素性检验） 判素和 Pollard's Rho（随机化‌的大整数分解） 算法。

四、唯一分解定理的核心应用

1. 约数个数定理

若 n=p1k1×p2k2×...×pmkmn = p₁^{k¹} × p₂^{k²} × ... × pₘ^{kᵐ} ，则 n 的正约数个数为：

d(n) = (k₁ + 1) × (k₂ + 1) × ... × (kₘ + 1)

原理：对于每个质因子 pᵢ，其指数可以取 0, 1, 2, ..., kᵢ 共 kᵢ+1 种选择。根据乘法原理，所有质因子的选择组合数就是约数个数。

示例：360 = 2³ × 3² × 5¹，约数个数 = (3+1) × (2+1) × (1+1) = 4 × 3 × 2 = 24个。

代码实现：

int divisorCount(int n) {
    int result = 1;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) {
                n /= i;
                cnt++;
            }
            result *= (cnt + 1);
        }
    }
    if (n > 1) result *= 2;   // 剩下一个大质因子，指数为1
    return result;
}

2. 约数和定理

若 n=p1k1×p2k2×...×pmkmn = p₁^{k¹} × p₂^{k²} × ... × pₘ^{kᵐ} ，则 n 的所有正约数之和为：

$σ(n) = (p₁⁰+p₁¹+...+p₁^{k¹}) × (p₂⁰+p₂¹+...+p₂^{k²}) × ... × (pₘ⁰+pₘ¹+...+pₘ^{kᵐ})$

即：

σ(n)=∏(pi(ki+1)−1)/(pi−1)σ(n) = ∏ (pᵢ^{(kᵢ+1) - 1) / (pᵢ - 1)}

代码实现：

long long divisorSum(int n) {
    long long result = 1;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) {
                n /= i;
                cnt++;
            }
            // 计算 1 + p + p^2 + ... + p^cnt
            long long term = 1, power = 1;
            for (int j = 1; j <= cnt; j++) {
                power *= i;
                term += power;
            }
            result *= term;
        }
    }
    if (n > 1) result *= (1 + n);   // 大质因子：1 + p
    return result;
}

3. 最大公约数与最小公倍数

利用唯一分解定理，GCD 和 LCM 可以用指数操作直接计算：

  • GCD：取公共质因子的最小指数，即 gcd(a,b)=∏pimin(αi,βi)gcd(a,b) = ∏ pᵢ^{min(αᵢ, βᵢ)}
  • LCM：取所有质因子的最大指数，即 lcm(a,b)=∏pimax(αi,βi)lcm(a,b) = ∏ pᵢ^{max(αᵢ, βᵢ)}

示例：

a = 12 = 2² × 3¹
b = 18 = 2¹ × 3²

gcd(12,18) = 2^min(2,1) × 3^min(1,2) = 2¹ × 3¹ = 6
lcm(12,18) = 2^max(2,1) × 3^max(1,2) = 2² × 3² = 36

4. 完全平方数判断

结论：n 是完全平方数 当且仅当 n 的标准分解式中所有质因子的指数都是偶数。

原理：若 n = m²，则 m 的分解式中每个质因子的指数是 n 中对应指数的一半，因此 n 中所有指数必为偶数。

代码实现：

bool isPerfectSquare(int n) {
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) {
                n /= i;
                cnt++;
            }
            if (cnt % 2 != 0) return false;   // 指数为奇数，不是完全平方数
        }
    }
    if (n > 1) return false;   // 剩一个大质因子，指数为1（奇数）
    return true;
}

5. 欧拉函数（了解）

唯一分解定理是欧拉函数计算公式的理论基础。若 n 的质因数分解为 n=p1k1×p2k2×...×pmkmn = p₁^{k¹} × p₂^{k²} × ... × pₘ^{kᵐ}，则：

φ(n) = n × (1 - 1/p₁) × (1 - 1/p₂) × ... × (1 - 1/pₘ)

φ(n) 表示 1~n 中与 n 互质的正整数的个数。

五、GESP五级真题精讲

真题1：因数分解（2023年9月）

题目描述：给定一个正整数 n，输出它的因数分解式。要求按质因数由小到大排列，乘号用 * 表示且左右各空一格；当且仅当一个素数出现多次时，将它们合并为指数形式，用 ^ 表示且左右不空格。

样例：

输入：20
输出：2^2 * 5

输入：23
输出：23

解题思路：试除法分解质因数，按格式输出。

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    bool first = true;   // 是否是第一个输出的质因子
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) {
                n /= i;
                cnt++;
            }
            if (!first) cout << " * ";
            first = false;

            if (cnt == 1) {
                cout << i;
            } else {
                cout << i << "^" << cnt;
            }
        }
    }
    // 处理最后剩下的大于√n的质因子
    if (n > 1) {
        if (!first) cout << " * ";
        cout << n;
    }
    cout << endl;
    return 0;
}

关键点：

  • first 标志控制乘号 * 的输出
  • 指数为1时不输出 ^1
  • 最后单独处理大于 √n 的质因子

真题2：小杨的幸运数字（2024年6月）

题目描述：小杨认为幸运数字应该恰好有两种不同的质因子。例如，12 = 2×2×3 的质因子有 2、3，恰好为两种不同的质因子，因此 12 是幸运数字；而 30 = 2×3×5 的质因子有 2、3、5，不符合要求。

解题思路：分解质因数，统计不同质因子的个数，判断是否恰好为2。

#include <iostream>
using namespace std;

void cal(int n) {
    int cnt = 0;   // 不同质因子的个数
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            cnt++;
            while (n % i == 0) n /= i;   // 除尽该质因子
        }
    }
    if (n > 1) cnt++;   // 剩下的大质因子
    if (cnt == 2) cout << 1 << endl;
    else cout << 0 << endl;
}

int main() {
    int T, x;
    cin >> T;
    while (T--) {
        cin >> x;
        cal(x);
    }
    return 0;
}

关键点：while (n % i == 0) n /= i; 确保同一个质因子只统计一次。数据范围 n ≤ 10⁴，每个数 ≤ 10⁶，试除法 O(√n) 完全可行。

真题3：奇妙数字（2024年12月）

题目描述：涉及质因数分解和约数个数的综合应用。

解题思路：利用约数个数定理 (k₁+1)×(k₂+1)×... 计算约数个数，再根据题目要求处理。

真题4：相等序列（2025年12月）

题目描述：给定一个序列，每次操作可以花费1金币，选择序列中一个数乘以质数 P 或除以质数 P（要求 P 能整除该数），目标使序列中所有数相同，求最少花费。

解题思路：乘以质数 P ⇔ 在质因数分解中增加 P 的指数；除以质数 P ⇔ 减少 P 的指数。不同质数的指数调整相互独立，可分别优化。

六、易错点汇总

  1. 循环条件写错：必须是 i * i <= n（即枚举到 √n），不是 i <= n。后者会超时。
  2. 忘记处理最后的质因子：循环结束后，如果 n > 1，说明剩下一个大于 √n 的质因子，必须单独输出。
  3. 统计不同质因子时未除尽：统计不同质因子个数时，必须用 while (n % i == 0) n /= i; 将同一质因子除尽，否则会重复计数。
  4. 指数为1时输出格式：因数分解（2023年9月） 要求指数为1时不输出 ^1，需要特判。
  5. 乘号输出控制：第一个质因子前不加乘号，后续质因子前加 *，用 first 标志控制。
  6. 约数个数忘记大质因子：约数个数定理中，最后剩下的大质因子指数为1，贡献 (1+1)=2。
  7. 完全平方数判断遗漏：最后剩下的大质因子指数为1（奇数），所以如果不是1则不是完全平方数。
  8. 数据范围判断：试除法适合 n ≤ 10⁹ 的情况。更大的数需要 Pollard's Rho 算法（五级不要求）。
  9. 特判 n = 1：1 不是质数也不是合数，不能分解为质数乘积。题目数据范围通常保证 n ≥ 2。
  10. 整数溢出：约数和的计算可能超出 int 范围，需要用 long long。

七、速查表

需求 写法 关键注意
质因数分解 试除法，i * i <= n 枚举到 √n
分解标准模板 for(i=2; i*i<=n; i++) if(n%i==0){ while(n%i==0){n/=i;cnt++;} } 统计指数
最后大质因子 if (n > 1) ... 指数为1
约数个数 (k₁+1)×(k₂+1)×...×(kₘ+1) 含大质因子时乘2
约数和 ∏ (pᵢ^(kᵢ+1)-1)/(pᵢ-1) 等比数列求和
GCD（分解法） 取公共质因子的最小指数 与辗转相除结果一致
LCM（分解法） 取所有质因子的最大指数 注意溢出
完全平方数 所有质因子指数为偶数 最后 n 必须为1
不同质因子个数 while(n%i==0) n/=i; 后计数 每个质因子只计一次
欧拉函数 φ(n) = n × ∏(1-1/pᵢ) 了解即可
试除法复杂度 O(√n) 适合 n ≤ 10⁹

八、总结

唯一分解定理是GESP五级数论模块的基石。记住十句话：

  1. 任何大于1的整数都能唯一分解为质数的乘积。
  2. 标准分解式： n=p1k1×p2k2×...×pmkmn = p₁^{k¹} × p₂^{k²} × ... × pₘ^{kᵐ}。
  3. 试除法分解：从2枚举到√n，反复除，记录指数。
  4. n 中最多只有一个大于 √n 的质因子，循环结束后单独处理。
  5. 约数个数 =(k1+1)×(k2+1)×...×(km+1)= (k₁+1) × (k₂+1) × ... × (kₘ+1)。
  6. 约数和 =∏(pi(ki+1)−1)/(pi−1)= ∏ (pᵢ^{(kᵢ+1)-1)/(pᵢ-1)}。
  7. GCD 取公共质因子的最小指数，LCM 取最大指数。
  8. 完全平方数 ⇔ 所有质因子指数为偶数。
  9. 统计不同质因子个数时，必须将同一质因子除尽再计数。
  10. 多练“因数分解格式输出”“不同质因子统计”“约数个数计算”三类题。

复习建议：先把试除法分解的标准模板写熟，确保能正确输出每个质因子的底数和指数；然后掌握约数个数和约数和公式，最后练习“完全平方数判断”“相等序列”等综合应用。考试中先判断题目是要求分解、计数还是求约数，注意循环边界和最后质因子的处理。