形式化题目

给定自然数 $A, B$（$0 \leqslant A, B \leqslant 5 \times 10^7$，不同时为 $0$），设

为 $A^B$ 的所有正约数之和，求 $S \bmod 9901$。

约定 $A = 0$ 时 $S = 0$（$0$ 的约数和不作数学定义，本题的评测数据即取这个约定值，见样例数据 0 50000000 输出 0）。

样例：$A = 2, B = 3$，$A^B = 8$，约数为 $1, 2, 4, 8$，$S = 15$，输出 15。

正解

思路

朴素想法：先算出 $A^B$，再枚举它的每个约数求和。样例里 $A = 2, B = 3$ 时 $A^B = 8$，约数 $1, 2, 4, 8$，和 $15$，没问题。但 $A = B = 5 \times 10^7$ 时 $A^B$ 有约 $B \log_{10} A \approx 3.8 \times 10^8$ 位十进制数字——光是把这个数存下来就超过 128 MB，枚举约数更不可能。瓶颈是 $A^B$ 这个数本身的规模，所以必须找到一个根本不写出 $A^B$ 的做法。

关键观察一：约数之和是乘性的。 把 $A$ 质因数分解为

$A^B$ 的每个正约数都唯一地写成 $\prod_i p_i^{a_i}$，其中 $0 \leqslant a_i \leqslant e_i B$。把这些选择展开成乘积：

右边每个括号只和一个质数 $p_i$、一个项数 $e_i B + 1$ 有关，与 $A^B$ 的位数毫无关系。以 $A = 12 = 2^2 \cdot 3$、$B = 1$ 为例（此时两个括号分别是 $1 + 2 + 2^2$ 与 $1 + 3$，项数 $3$ 和 $2$），$12$ 的约数正好是下表 3 × 2 的全部格子：

行下标 $i$ 穷举了质数 2 的指数，列下标 $j$ 穷举了质数 3 的指数，所以格子里恰好是 $2^{i}3^{j}$ 形式的全部约数。按行求和得 $(1+3), (2+6), (4+12)$，总和为 $(1+2+4)(1+3) = 7 \times 4 = 28$，与直接枚举 $1+2+3+4+6+12 = 28$ 一致——“每个约数唯一地写成 $2^i 3^j$”正是括号相乘的依据。本题样例 $A = 2, B = 3$ 只有一个质因子，项数 $= 1 \times 3 + 1 = 4$，同样是 $1 + 2 + 4 + 8 = 15$。

关键观察二：$A$ 本身很小，可以直接分解。 $A \leqslant 5 \times 10^7$，试除到 $\sqrt{A} \approx 7071$ 就能完成分解，剩下的 $n > 1$ 必是质数。这一步完全避开了 $A^B$。

瓶颈转移：现在只需要求一个等比和

但 $m$ 最大可达 $25 \times 5 \times 10^7 + 1 \approx 1.3 \times 10^9$，逐项累加仍然太慢。于是要找把 $m$ 快速变小的递推。

关键观察三：项数翻倍只需一次乘法。 记 $f_m = 1 + p + \cdots + p^{m-1}$、$g_m = p^m$。前 $m$ 项与后 $m$ 项之间只差一个 $p^m$：

项数多出一项时再补上第 $2m$ 项（它就是 $p^{2m}$）：

每一步都把已经确定的项数从 $m$ 翻倍到 $2m$，或在翻倍后加一——这正好与 $m$ 的二进制位对应：从最高位读到最低位，每读一位先做 $m \to 2m$ 的翻倍，读到 1 再补一项。于是 $m$ 的二进制位数（最多 31 位）就是轮数，$O(\log m)$ 完成。

以 $p = 3$、$m = 5 = (101)_2$ 为例：

每一行的 $f$ 都是把上一行翻倍（10 行：$1 \times (3+1) = 4$）、再按当前位是否为 1 决定要不要补一项（101 行：$4 \times (9+1) = 40$，再补第 4 项 $81$ 得 $121$）得到的；$g$ 始终是 $p$ 的当前次幂。最后一行 $f = 121$ 正是 $1+3+9+27+81$，说明这条递推确实一次不落地累加了全部 $m$ 项。

为什么不用 $(p^k-1)/(p-1)$：那个公式要除以 $p-1$，只有当 $\gcd(p-1, 9901) = 1$ 时才能在模意义下求逆元。只要 $p \equiv 1 \pmod{9901}$（例如 $A = 59407 = 6 \times 9901 + 1$），$p - 1$ 就是模数的倍数，逆元不存在，除法版公式会直接失效。上面的递推只用乘法、加法和取模，对任意 $p$、任意项数都成立。

算法流程：$A = 0$ 直接输出 0；否则分解 $A$，对每个 $(p_i, e_i)$ 用位递推求出项数 $e_i B + 1$ 的等比和（$p_i$ 先对 9901 取模），再把所有结果相乘取模输出。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 09:57
# update_at: 2026-10-01 09:57

import sys
from collections.abc import Iterator

MOD = 9901  # 题面要求的取模常量


def factors(n: int) -> Iterator[tuple[int, int]]:
    """分解 n = ∏ p^e，依次产出 (p, e)。"""
    small = [p for p in (2, 3, 5) if n % p == 0]  # 先摘掉小质因子，省去开头的试探
    for p in small:
        e = 0
        while n % p == 0:
            n //= p
            e += 1
        yield p, e
    d = 7  # 已排除 2、3、5，剩下的质因子都落在 6k±1 上
    while d * d <= n:
        for p in (d, d + 4):  # 6k+1 与 6k+5 构成一对候选
            if n % p == 0:
                e = 0
                while n % p == 0:
                    n //= p
                    e += 1
                yield p, e
        d += 6
    if n > 1:  # 除完小因子后剩下的必然是质数
        yield n, 1


def divsum(p: int, terms: int) -> int:
    """等比数列 1+p+…+p^(terms-1) 对 9901 取模：按 terms 的二进制从高位往低位折半。"""
    f, g = 0, 1  # f = 1+p+…+p^(k-1)，g = p^k；k 是已经确定的项数
    for bit in bin(terms)[2:]:
        f, g = f * (g + 1) % MOD, g * g % MOD  # 项数翻倍：两段长度 k 的等比串首尾相接
        if bit == "1":  # 二进制这一位是 1：末尾再补一项 p^(2k)
            f, g = (f + g) % MOD, g * p % MOD
    return f


def sum_of_divisors(a: int, b: int) -> int:
    """求 A^B 的所有约数之和 mod 9901。"""
    if a == 0:  # 0 被所有正整数整除，约数和不是有限值；本题数据约定答案为 0
        return 0
    ans = 1
    for p, e in factors(a):  # A^B = ∏ p^(e·b)，各质因子的等比和彼此独立
        ans = ans * divsum(p % MOD, e * b + 1) % MOD  # 等比和共有 e·b+1 项
    return ans


def solve() -> None:
    a, b = map(int, sys.stdin.buffer.read().split())
    print(sum_of_divisors(a, b))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 13:44
 * update_at: 2026-10-06 13:44
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll MOD = 9901; // 题面要求的取模常量

// 求等比和 1 + p + ... + p^(terms-1) 对 MOD 取模。
// 按 terms 的二进制从高位读到低位：每读一位先让项数翻倍，再决定是否补一项。
ll divsum(ll p, ll terms) {
    ll f = 0; // f = 1 + p + ... + p^(k-1)，k 是已经确定的项数
    ll g = 1; // g = p^k
    for (ll bit = 1LL << 40; bit > 0; bit >>= 1) {
        f = f * (g + 1) % MOD; // 项数翻倍：两段长度为 k 的等比串首尾相接
        g = g * g % MOD;
        if (terms & bit) {     // 当前位是 1：末尾再补一项 p^(2k)
            f = (f + g) % MOD;
            g = g * p % MOD;
        }
    }
    return f;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll a, b;
    cin >> a >> b;

    if (a == 0) { // 本题数据约定：0 的约数和取 0
        cout << 0 << "\n";
        return 0;
    }

    // 分解 A = ∏ p^e，对每个质因子的等比和相乘
    ll ans = 1;
    ll n = a;
    for (ll p = 2; p * p <= n; p++) {
        if (n % p != 0) continue;
        ll e = 0;
        while (n % p == 0) {
            n /= p;
            e++;
        }
        ans = ans * divsum(p % MOD, e * b + 1) % MOD; // 该括号共有 e*B+1 项
    }
    if (n > 1) { // 除完小因子后剩下的部分本身就是质数，指数为 1
        ans = ans * divsum(n % MOD, b + 1) % MOD;
    }

    cout << ans << "\n";
    return 0;
}

代码分三层：factors 负责试除分解（先摘掉 2、3、5，再按 $6k \pm 1$ 试除，剩余部分 $> 1$ 时它自己就是质数）；divsum 是上面 $(f, g)$ 的位递推，只有乘法、加法和取模，不涉及逆元；sum_of_divisors 做乘性合并，并特判 $A = 0$。p % MOD 在调用处完成，因此 divsum 内部不需要额外的取模保护。

复杂度

• 时间：$O(\sqrt{A} + k \log(eB))$（$k$ 是 $A$ 的不同质因子个数）。分解最多约 $2.4 \times 10^3$ 次试除；每个质因子的 divsum 至多 31 轮（项数 $eB + 1 \leqslant 1.25 \times 10^9 < 2^{31}$）；质因子个数 $k \leqslant 8$（$2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 = 9699690$，再乘 23 就超过 $5 \times 10^7$）。实测最坏数据 0.02 s 内出结果。
• 空间：$O(1)$。factors 是生成器，不保存因子表；divsum 只维护两个小于 9901 的整数。

总结

本题的解法可以概括为三步替换：

1. 把"算出 $A^B$ 再枚举约数"换成 约数和公式 $\sigma(A^B) = \prod_i (1 + p_i + \cdots + p_i^{e_i B})$，让指数只以乘积形式出现，彻底回避 $10^8$ 位的大数；
2. 把每个括号的逐项累加换成 项数翻倍的折半递推 $f_{2k} = f_k (1 + g_k)$，把 $O(eB)$ 降到 $O(\log(eB))$；
3. 把"除以 $p-1$"换成纯乘加的递推，避免 $p \equiv 1 \pmod{9901}$ 时逆元不存在。

前两步分别对应「数论里的乘性结构」和「分治/倍增思想」，第三步则是模板题里最容易踩的坑：凡是模意义下的除法，都要先确认分母与模数互质。