当前位置：首页 > 洛谷 > 洛谷P1593题解：质因数分解与快速幂优化求解

洛谷P1593题解：质因数分解与快速幂优化求解

2个月前 (07-27)

一、题目解读

洛谷P1593题是一道涉及数学推导与算法优化的题目，要求计算给定整数a的b次方各质因数的乘积，并对结果取模9901。题目核心在于将指数运算转化为质因数分解，结合等比数列求和公式求解，需兼顾时间复杂度与高精度计算。

二、解题思路

通过以下思路解题：

1. 质因数分解：将a分解为质因数乘积形式（如a = p1^c1 * p2^c2 *...），每个质因数pi的指数为ci。

2. 转化数学公式：将a^b分解为各质因数pi的b次方乘积，即求Σ(p_i^b)。

3. 等比数列求和：每个质因数的贡献可转化为等比数列求和公式（1 + p + p^2 +... + p^(c*b))，利用递归分治优化计算复杂度。

4. 快速幂优化：为避免大数溢出，使用快速幂算法计算幂次结果并取模。

三、解题步骤

1. 输入处理：读取a和b，若a=0直接返回0。

2. 质因数分解：从2开始遍历至√a，统计每个质因数i的出现次数cnt。

3. 递归计算：调用sum函数计算每个质因数i的等比数列和sum(i, cnt*b)，乘积累乘至res。

4. 特殊处理：若分解后a仍大于1（剩余大质因数），单独计算其贡献。

5. 结果输出：输出res对MOD取模的结果。

四、代码与注释

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

const int MOD = 9901; // 模数

// 快速幂计算 (base^exp) % MOD
long long qpow(long long base, long long exp) {
    long long res = 1;
    while (exp) {
        if (exp & 1) res = res * base % MOD; // 若指数为奇数，累乘
        base = base * base % MOD; // 底数平方优化
        exp >>= 1; // 右移等价于除以2
    }
    return res;
}

// 计算等比数列和 (1 + p + p^2 +... + p^e) % MOD
long long sum(long long p, long long e) {
    if (e == 0) return 1; // 边界：e=0时和为1
    if (p == 0) return 0; // p=0时和为0
    
    if (e % 2 == 1) { // 奇数项：拆分为中间项乘前半部分
        return (1 + qpow(p, (e+1)/2)) * sum(p, (e-1)/2) % MOD;
    } else { // 偶数项：拆分为前半部分乘中间项 + p^e
        return ((1 + qpow(p, e/2)) * sum(p, e/2-1) + qpow(p, e)) % MOD;
    }
}

int main() {
    int a, b;
    cin >> a >> b;
    
    if (a == 0) { // 特判a=0
        cout << 0 << endl;
        return 0;
    }
    
    int res = 1; // 结果初始化
    for (int i = 2; i*i <= a; i++) { // 质因数分解
        if (a % i == 0) {
            int cnt = 0;
            while (a % i == 0) { // 统计质因数i的个数
                a /= i;
                cnt++;
            }
            res = res * sum(i, cnt * b) % MOD; // 累乘每个质因数的贡献
        }
    }
    if (a > 1) { // 剩余大质因数单独处理
        res = res * sum(a, b) % MOD;
    }
    
    cout << res << endl;
    return 0;
}

注释说明：代码通过快速幂减少计算量，递归sum函数利用分治思想优化等比数列求和，质因数分解避免重复计算，最终结果取模保证正确性。