C++ 核心知识点笔记：唯一分解定理与 pair 容器

一、唯一分解定理（质因数分解）

1. 什么是唯一分解定理？

唯一分解定理（也叫算术基本定理）是指：任何一个大于1的自然数，要么本身就是质数，要么可以分解为几个质数的乘积，而且这种分解方式是唯一的（不考虑质因数的顺序）。

例如：

• 12 = 2×2×3（也可写成 2²×3）
• 36 = 2×2×3×3（也可写成 2²×3²）

2. 质因数分解的实现思路

分解质因数的基本步骤：

1. 从最小的质数2开始，尝试整除目标数
2. 记录该质数能整除的次数（指数）
3. 整除完成后，目标数缩小，继续用下一个数尝试
4. 直到目标数被分解为1为止
5. 如果最后剩余的数大于1，说明它本身是一个质数

3. 代码实现（带详细注释）

#include <iostream>
#include <vector>
using namespace std;

// 函数功能：对正整数n进行质因数分解
// 返回值：vector容器，每个元素是pair类型（质因数, 指数）
vector<pair<int, int>> primeFactorization(int n) {
    vector<pair<int, int>> factors;  // 存储分解结果的容器
    
    // 从2开始尝试分解，i*i <= n是优化条件（大于平方根的因数无需重复判断）
    for (int i = 2; i * i <= n; ++i) {
        int exponent = 0;  // 记录当前质数i的指数
        
        // 循环除以i，计算能整除的次数
        while (n % i == 0) {
            n /= i;        // 每次整除后n缩小
            ++exponent;    // 指数加1
        }
        
        // 如果指数大于0，说明i是n的质因数，存入容器
        if (exponent > 0) {
            // 两种添加方式：
            // factors.emplace_back(i, exponent);  // 直接构造pair
            factors.push_back(make_pair(i, exponent));  // 显式创建pair
        }
    }
    
    // 如果循环结束后n仍大于1，说明剩余的n是一个质数
    if (n > 1) {
        factors.emplace_back(n, 1);  // 该质数的指数为1
    }
    
    return factors;  // 返回分解结果
}

int main() {
    int num;
    cout << "请输入一个正整数: ";
    cin >> num;
    
    // 调用分解函数，用auto自动推断返回值类型
    auto result = primeFactorization(num);
    
    // 输出分解结果
    cout << num << " 的唯一分解形式为: ";
    for (size_t i = 0; i < result.size(); ++i) {
        // 输出质因数（pair的第一个元素）
        cout << result[i].first;
        
        // 如果指数大于1，输出指数（pair的第二个元素）
        if (result[i].second > 1) {
            cout << "^" << result[i].second;
        }
        
        // 不是最后一个元素时，添加乘号分隔
        if (i < result.size() - 1) {
            cout << " * ";
        }
    }
    cout << endl;
    
    return 0;
}

4. 代码执行示例

输入：36
输出：36 的唯一分解形式为: 2^2 * 3^2

输入：12
输出：12 的唯一分解形式为: 2^2 * 3

二、C++ pair 容器详解

1. 什么是 pair？

pair 是 C++ 标准库中的一个模板类，它可以将两个不同类型的数据打包成一个单元，相当于一个"二元组"。

可以把 pair 想象成一个"双胞胎盒子"：

• 第一个格子放数据A（用 first 访问）
• 第二个格子放数据B（用 second 访问）

2. pair 的基本使用

（1）头文件与命名空间

使用 pair 需要包含头文件 <utility>，通常配合 using namespace std; 简化代码。

#include <iostream>
#include <utility>  // 必须包含的头文件
using namespace std;

（2）创建 pair 的三种方式

int main() {
    // 方式1：直接声明并初始化（指定类型）
    pair<int, string> p1(10, "apple");  // 第一个元素int，第二个元素string
    
    // 方式2：先声明后赋值
    pair<double, char> p2;
    p2.first = 3.14;    // 访问并修改第一个元素
    p2.second = 'A';    // 访问并修改第二个元素
    
    // 方式3：使用make_pair函数（自动推断类型，推荐）
    auto p3 = make_pair(2023, 5.20);  // 自动识别为pair<int, double>
    
    return 0;
}

（3）访问 pair 中的元素

通过 first 和 second 成员访问两个元素：

int main() {
    pair<string, int> student("小明", 95);  // 姓名+分数
    
    cout << "姓名：" << student.first << endl;   // 输出第一个元素：小明
    cout << "分数：" << student.second << endl;  // 输出第二个元素：95
    
    return 0;
}

3. pair 作为函数参数和返回值

pair 非常适合让函数返回两个相关的值，无需使用全局变量。

// 函数功能：计算两数的和与差，返回一个pair
pair<int, int> calculate(int a, int b) {
    int sum = a + b;
    int diff = a - b;
    return make_pair(sum, diff);  // 返回打包后的结果
}

int main() {
    auto result = calculate(15, 7);  // 接收返回的pair
    cout << "和：" << result.first << endl;   // 输出22
    cout << "差：" << result.second << endl;  // 输出8
    return 0;
}

4. pair 的比较运算

pair 之间可以直接比较，比较规则：

• 先比较第一个元素，若不相等则直接得出结果
• 若第一个元素相等，再比较第二个元素

int main() {
    pair<int, char> p1(2, 'a');
    pair<int, char> p2(2, 'b');
    pair<int, char> p3(3, 'a');
    
    cout << (p1 < p2) << endl;  // 输出1（true），因为'a' < 'b'
    cout << (p1 < p3) << endl;  // 输出1（true），因为2 < 3
    cout << (p2 == p3) << endl; // 输出0（false）
    return 0;
}

5. pair 的常见用途

1. 存储关联数据：如（ID, 姓名）、（坐标x, 坐标y）
2. 函数返回多个值：避免使用全局变量或指针
3. 作为容器元素：在 map、set 等容器中存储键值对
4. 质因数分解：如本文开头的例子，存储（质数, 指数）

三、综合练习：质因数分解的另一种输出形式

题目要求：将36分解为 "36=223*3" 形式（而非指数形式）

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int temp = n;  // 保存原始值用于输出
    int i = 2;     // 从最小质数开始尝试
    bool isFirst = true;  // 标记是否是第一个质因数
    
    cout << temp << "=";
    
    // 循环分解直到n变为1
    while (n != 1) {
        // 找到能整除的质数
        while (n % i == 0) {
            // 控制输出格式（第一个元素前不加*）
            if (isFirst) {
                cout << i;
                isFirst = false;
            } else {
                cout << "*" << i;
            }
            n /= i;  // 缩小n的值
        }
        i++;  // 尝试下一个数
    }
    cout << endl;
    return 0;
}

总结

1. 唯一分解定理：任何大于1的自然数都能唯一分解为质数的乘积
2. 质因数分解的核心是循环尝试整除，记录质数和其指数
3. pair 是处理二元数据的实用工具，通过 first 和 second 访问元素
4. pair 常用于函数返回多值、存储关联数据和容器元素

通过这两个知识点的结合，可以高效地实现质因数分解并清晰地存储结果，这也是 C++ 中"数据结构+算法"结合的典型例子。