2023年GESP五级题「因式分解」洛谷B3871算法解析与代码实现

一、题目解读

2023年GESP五级题「因式分解」（洛谷B3871）要求将给定的大整数N分解为质因数的乘积形式，并输出每个质因数及其指数。题目考察核心算法为质因数分解，需高效处理大数分解，避免超时。难点在于如何优化分解过程，减少循环次数，同时准确记录每个质因数的出现次数。

二、解题思路

用户提供的代码采用试除法进行质因数分解，核心逻辑分为三步：

1. 优先处理2因子：由于2是唯一的偶质数，单独处理可减少后续循环次数。通过循环除以2，统计其出现次数。

2. 处理奇数因子：从3开始，以步长2遍历奇数（跳过偶数），利用sqrt(n)优化上限，减少遍历范围。

3. 处理剩余大质数：若分解后n仍大于1，说明剩余部分为大于sqrt(n)的质数，直接作为单个因子加入结果。

该思路通过分阶段处理，结合数学优化（如sqrt减少遍历范围），实现高效分解。

三、解题步骤

1. 输入：读取用户输入的整数N。

2. 质因数分解：调用factorize(N)函数，利用试除法分解N，结果存入vector<pair<long long, int>>（质因数+指数）。

3. 输出结果：遍历结果vector，拼接质因数表达式（如2^3 * 3^2）。

4. 边界处理：若N为质数或剩余大质数，单独处理其指数为1的情况。

四、代码与注释

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

// 质因数分解函数
vector<pair<long long, int>> factorize(long long n) {
    vector<pair<long long, int>> factors;
    
    // 处理2的因子
    if (n % 2 == 0) { // 优先处理2，减少后续循环次数
        int cnt = 0;
        while (n % 2 == 0) {
            n /= 2;
            cnt++; // 统计2的个数
        }
        factors.emplace_back(2, cnt); // 添加至结果
    }
    
    // 处理奇数因子
    for (long long i = 3; i <= sqrt(n); i += 2) { // 仅遍历奇数，优化范围
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) {
                n /= i;
                cnt++;
            }
            factors.emplace_back(i, cnt); // 添加质因数及其指数
        }
    }
    
    // 处理剩余的大质数（若n仍未1，说明其为大于sqrt(n)的质数）
    if (n > 1) {
        factors.emplace_back(n, 1);
    }
    
    return factors;
}

int main() {
    long long N;
    cin >> N;
    
    auto factors = factorize(N);
    bool first = true;
    
    // 输出格式：质因数^指数，用*分隔
    for (const auto& [prime, exp] : factors) {
        if (!first) {
            cout << " * ";
        }
        first = false;
        
        cout << prime;
        if (exp > 1) {
            cout << "^" << exp;
        }
    }
    
    cout << endl;
    return 0;
}

五、总结

1. 算法效率：通过优先处理2因子、奇数遍历步长2、sqrt优化上限，该代码在时间复杂度上远优于暴力枚举，适用于大数分解场景。

2. 代码优化点：

    使用vector动态存储因子，避免固定数组长度限制。

    利用C++11的结构化绑定（[prime, exp]）简化迭代输出。

3. 扩展思考：对于更复杂的大数分解问题，可结合筛法（如埃氏筛）预处理质数表，进一步提升效率。

该题目解法不仅是GESP竞赛的典型考点，也为学习数学与编程结合的算法思维提供了优秀案例。