因子和

题目解析

这是一个非常经典的数论题目，考察了 唯一分解定理 (Prime Factorization)、约数和公式 (Sum of Divisors) 以及 同余运算 (Modular Arithmetic) 的综合应用。

1. 核心数学原理

第一步：唯一分解定理

任意一个大于 1 的整数 $A$ 都可以唯一分解为若干个质数的乘积：

A = p_1^{c_1} \times p_2^{c_2} \times \dots \times p_k^{c_k}

那么， $A^B$ 的分解形式就是：

A^B = p_1^{c_1 \cdot B} \times p_2^{c_2 \cdot B} \times \dots \times p_k^{c_k \cdot B}

第二步：约数和公式

对于一个数 $N = p_1^{e_1} \times p_2^{e_2} \times \dots$ ，其所有约数的和 $\text{sum}(N)$ 为：

\text{sum}(N) = (1 + p_1 + p_1^2 + \dots + p_1^{e_1}) \times \dots \times (1 + p_k + \dots + p_k^{e_k})

对应到我们的题目，令 $M_i = c_i \cdot B$ ，则 $A^B$ 的约数和为：

\text{Ans} = \prod_{i=1}^{k} \sum_{j=0}^{M_i} p_i^j

第三步：等比数列求和

每一项 $(1 + p + p^2 + \dots + p^M)$ 都是一个等比数列求和。

根据求和公式：

S = \frac{p^{M+1} - 1}{p - 1}

我们需要计算这个结果对 $9901$ 取模。

2. 难点与特殊情况处理

我们需要计算 $\frac{p^{M+1} - 1}{p - 1} \pmod{9901}$ 。在模运算中，除法需要转化为乘以“逆元”。

这里分为两种情况：

情况 A： $p - 1$ 不是 $9901$ 的倍数
- 也就是说 $p \pmod{9901} \neq 1$ 。
- 因为 $9901$ 是一个质数（你可以写个小程序验证一下，或者相信题目），我们可以使用 费马小定理 求逆元。
- $(p-1)$ 的逆元为 $(p-1)^{9901-2} \pmod{9901}$ 。
- 公式变为： $(p^{M+1} - 1) \times \text{qpow}(p-1, 9901-2) \pmod{9901}$ 。
情况 B： $p - 1$ 是 $9901$ 的倍数
- 也就是说 $p \equiv 1 \pmod{9901}$ 。
- 此时不能使用除法公式（分母为 0）。
- 但是回到原始的求和式子： $1 + p + p^2 + \dots + p^M$ 。
- 因为 $p \equiv 1$ ，所以每一项都变成了 1。
- 一共有 $M+1$ 项。
- 结果直接为 $(M + 1) \pmod{9901}$ 。

3. 算法流程

特判：如果 $A=0$ ，输出 0；如果 $B=0$ ，输出 1。
质因数分解：对 $A$ 进行质因数分解，得到所有的 $(p_i, c_i)$ 。
计算每一部分：对于每个质因子 $p_i$ ，计算等比数列的和，并累乘到答案中。
输出：最终结果。

4. AC 代码 (C++)sum_of_factors.cpp12月31日 23:18

5. 代码解析与易错点

取模的时机：
- 在快速幂 qpow 内部，base 一开始就要取模。
- 在计算分子 numerator 时，减法可能会导致负数，所以必须写成 (a - b + MOD) % MOD。
逆元存在的条件：
- 一定要特判 (p % MOD) == 1 的情况。如果不特判，分母 p-1 模 9901 为 0，求逆元会得到错误结果或者除零错误。
- 注意是 p % MOD == 1，不是 p == 1。比如 $p = 9902$ 时，它模 9901 也是 1。
数据范围：
- $A, B$ 最大 $5 \times 10^7$ 。
- 分解质因数只循环到 $\sqrt{A} \approx 7071$ ，速度非常快。
- 指数部分 $count \times B$ 可能会超过 int 范围，所以涉及指数的变量最好开 long long。
$A=0$ 的情况：
- 虽然题目约定 $A \ge 1$ ，但如果 $A$ 能取 0，要特判。如果 $A=0$ ，没有因子和（或者说由定义决定），通常输出 0。
- $B=0$ 时， $A^0=1$ ，因子和为 1。

代码

cpp

/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2026-01-01 09:16:32
 */
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const int maxn = 2e6+5;
const int mod = 9901;
int n,m;
ll a,b;

//快速幂
ll quick_pow(ll base,ll exp) {
    ll res = 1;

    for(  ; exp ; exp >>= 1 )
    {
        //是1就乘
        if( exp & 1) res = (res * base ) % mod;

        // base 增增
        base = (base * base) %mod;
    }
    return res;
}



// 计算等比数列前 n+1 项和: 1 + p + ... + p^n
// 公式: (p^(n+1) - 1) / (p - 1)
ll _sum(ll p, ll n) {
    if( (p % mod) == 1 ) {
        return (n+1) % mod;
    }

    ll num = (quick_pow(p,n+1) - 1 +mod) %mod;
    ll fen_mu = (p-1) %mod;

    //求逆元
    ll inv = quick_pow(fen_mu, mod-2);
    return (num * inv) % mod;
}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    std::cin >> a >> b;
    if( a == 0) 
    {
        std::cout << 0 << "\n";
        return 0;
    }

    if (b== 0) {
        std::cout << 1 << "\n";
        return 0;
    }

    ll ans = 1;

    // 分解质因数
    for(int i = 2 ; i*i <= a; ++i)
    {
        if( a % i == 0) 
        {
            ll cnt = 0;
            while( a % i == 0) cnt++ ,a /=i;

            // 我们需要计算 1 + p + ... + p^(count*B)
            ll sum_ans = _sum(i, cnt * b);

            ans *= sum_ans;
            ans %= mod;

        }
    }

    //剩余部分
    if( a > 1) {
        ll sum_ans = _sum(a, b);
        ans *= sum_ans;
        ans %= mod;
    }
    
    std::cout << ans << "\n";
    return 0;
}

目录