因子和

题意

求 a^b 的所有正因子之和，对 9901 取模。

思路

若 $a=\prod p_i^{c_i}$ ，则 $a^b=\prod p_i^{c_i b}$ 。每个约数可以独立选择每个质因子的指数，所以因子和为：

\prod_i(1+p_i+p_i^2+\cdots+p_i^{c_i b})

不能无条件使用等比数列除法，因为 p-1 可能在模 9901 下没有逆元。代码用分治函数返回前 terms 项所需的两个量：

text

1(p^terms, 1+p+...+p^(terms-1))

已知一半的幂 power 和和 total，偶数项可合并成 total*(1+power)；奇数项再补最后一个幂。递归深度只有 $O(\log terms)$ ，且完全不需要除法。

Python 知识

函数返回二元组，同时复用分治计算出的幂和等比和。
Python 的递归深度在这里安全，因为指数最多带来几十层二分。
每次乘法立即 % MOD，控制中间整数大小。
count*exponent+1 是等比数列的项数，不是最高指数。
/home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md：递归深度和整数取模。
/home/rainboy/mycode/hugo-blog/content/program_language/python/map_reduce_filter.md：把各质因子贡献归约成乘积。

代码

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
36import sys


MOD = 9901


def power_and_sum(base, terms):
    if terms == 0:
        return 1, 0
    half_power, half_sum = power_and_sum(base, terms // 2)
    power = half_power * half_power % MOD
    total = half_sum * (1 + half_power) % MOD
    if terms % 2:
        return power * base % MOD, (total + power) % MOD
    return power, total


def main():
    number, exponent = map(int, sys.stdin.buffer.read().split())
    answer = 1
    prime = 2
    while prime * prime <= number:
        if number % prime == 0:
            count = 0
            while number % prime == 0:
                number //= prime
                count += 1
            answer = answer * power_and_sum(prime % MOD, count * exponent + 1)[1] % MOD
        prime += 1
    if number > 1:
        answer = answer * power_and_sum(number % MOD, exponent + 1)[1] % MOD
    print(answer)


if __name__ == "__main__":
    main()

cpp

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/**
 * P1593 因子和
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

const int MOD = 9901;

// 快速幂
long long qpow(long long a, long long b) {
    long long r = 1;
    while (b) {
        if (b & 1) r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}

// 等比数列求和：1 + p + p^2 + ... + p^k  mod MOD
long long geo_sum(long long p, long long k) {
    if (k == 0) return 1;
    if (k % 2 == 1) // 奇数项：1 + p + ... + p^k = (1 + p^(k/2+1)) * (1 + p + ... + p^(k/2))
        return (1 + qpow(p, k / 2 + 1)) * geo_sum(p, k / 2) % MOD;
    else // 偶数项：1 + p + ... + p^k = p^(k/2) + (1 + p^(k/2+1)) * (1 + p + ... + p^(k/2-1))
        return (qpow(p, k / 2) + (1 + qpow(p, k / 2 + 1)) * geo_sum(p, k / 2 - 1)) % MOD;
}

int main() {
    long long a, b;
    scanf("%lld%lld", &a, &b);
    if (a == 0) { puts("0"); return 0; }
    long long ans = 1;
    // 分解质因数
    for (long long p = 2; p * p <= a; ++p) {
        if (a % p == 0) {
            long long cnt = 0;
            while (a % p == 0) { a /= p; ++cnt; }
            ans = ans * geo_sum(p % MOD, cnt * b) % MOD;
        }
    }
    if (a > 1) ans = ans * geo_sum(a % MOD, b) % MOD;
    printf("%lld\n", ans % MOD);
    return 0;
}

复杂度

分解 a 需要 $O(\sqrt a)$ ，每个质因子的等比和需要 $O(\log(cb))$ ；额外空间是分治递归栈 $O(\log b)$ 。

总结

唯一分解把因子和拆成等比数列乘积；用“幂与和一起算”的分治形式，可以避开模逆元的特殊情况。

目录

题意

思路

Python 知识

代码

复杂度

总结