「一本通 6.6 练习 2」方程的解

形式化题目

给定正整数 $k$ 与 $x$ （ $k \geqslant 2$ ），定义：

g(x) = x^x \bmod 1000

求满足下列条件的不定方程的正整数解 $(a_1, a_2, \ldots, a_k)$ 的组数：

a_1 + a_2 + \cdots + a_k = g(x), \quad a_i \in \mathbb{N}^*

题目保证 $k \leqslant g(x)$ 。

正解

思路

本题分为两个独立的计算步骤：

计算常数项 $g(x)$ ：目标值为 $g(x) = x^x \bmod 1000$ 。虽然 $x < 2^{31}$ 数值较大，但由于只对模数 $1000$ 取模，可以使用整数快速幂在 $O(\log x)$ 时间内求出 $g(x)$ 。因为 $1000$ 是较小的模数，计算出的 $g(x)$ 满足 $0 \leqslant g(x) < 1000$ 。题面保证 $k \leqslant g(x)$ ，因此 $g(x) \geqslant k \geqslant 2$ 。
隔板法求不定方程正整数解的个数：问题转化为将正整数 $N = g(x)$ 拆分成 $k$ 个正整数之和的方案数：
$a_1 + a_2 + \cdots + a_k = N, \quad a_i \geqslant 1$
这等价于将 $N$ 个相同的小球排成一列，在它们形成的 $N - 1$ 个间隔中放置 $k - 1$ 块隔板，将小球分成非空的 $k$ 段。因此，满足条件的正整数解组数即为组合数：
$\binom{N - 1}{k - 1} = \binom{g(x) - 1}{k - 1}$
数值范围与精度：数据范围中 $k \leqslant 100$ ， $g(x) < 1000$ 。组合数 $\binom{g(x) - 1}{k - 1}$ 的最大值可能达到几百位数字，远超 $64$ 位整型范围，需要高精度计算。在 Python 中，内置整型天然支持任意精度大整数，且标准库 math.comb(n, k) 提供了高效的组合数实现。

图示解析

以 $g(x) = 6, k = 3$ （求 $a_1 + a_2 + a_3 = 6$ 的正整数解组数）为例，将 $6$ 个小球排成一行，在 $5$ 个间隔中选 $2$ 个位置插入隔板：

text

1
2
3
4小球序列：  ( 1 )  |  ( 2 )   ( 3 )   ( 4 )  |  ( 5 )   ( 6 )
间隔编号：       1         2       3       4         5
所选间隔：    [选 1]                     [选 4]
对应解组：    a1 = 1           a2 = 3              a3 = 2

从 $N - 1 = 5$ 个间隔中任意选取 $k - 1 = 2$ 个隔板，方案总数为 $\binom{5}{2} = 10$ 。

代码

Python 版：

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#!/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 00:07
# update_at: 2026-10-01 00:07

import math
import sys

MOD = 1000  # 方程右端 g(x) 的取模常数


def count_positive_solutions(variables: int, total: int) -> int:
    """隔板法求 total 分成 variables 个正整数之和的解组数，即 C(total - 1, variables - 1)。"""
    return math.comb(total - 1, variables - 1)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    k, x = next(data), next(data)

    # 题目给定 g(x) = x^x mod 1000
    target_sum = pow(x, x, MOD)
    ans = count_positive_solutions(k, target_sum)

    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92/**
 * 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 00:42
 * update_at: 2026-10-06 00:42
 */
#include <cstdio>

typedef long long ll;

const int MOD_G = 1000;        // g(x) = x^x 对 1000 取模
const int BASE = 1000000000;   // 高精度每段保存 9 位十进制数
const int MAXD = 64;           // C(998, 99) 约 139 位十进制，64 段足够

ll big[MAXD]; // 高精度数，从低位到高位每段压 9 位，big[0] 为最低段
ll big_len;   // 当前占用的段数

// 计算 (base^exp) mod mod，用二进制快速幂，只保留低位常数。
ll power_mod(ll base, ll exp, ll mod) {
    ll res = 1 % mod;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) {
            res = res * base % mod;
        }
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

// 高精度数乘以一个较小整数 mult（mult 不超过 1000），结果原地保存在 big[]。
void big_mul_small(ll mult) {
    ll carry = 0;
    for (ll i = 0; i < big_len; i++) {
        ll cur = big[i] * mult + carry;
        big[i] = cur % BASE;
        carry = cur / BASE;
    }
    while (carry > 0) {
        big[big_len] = carry % BASE;
        carry /= BASE;
        big_len++;
    }
}

// 高精度数整除一个较小整数 divisor（divisor 不超过 100），结果原地保存在 big[]。
void big_div_small(ll divisor) {
    ll rem = 0;
    for (ll i = big_len - 1; i >= 0; i--) {
        ll cur = rem * BASE + big[i];
        big[i] = cur / divisor;
        rem = cur % divisor;
    }
    while (big_len > 1 && big[big_len - 1] == 0) {
        big_len--;
    }
}

// 求组合数 C(M, K)。逐步用 C(M-K+i, i) = C(M-K+i-1, i-1) * (M-K+i) / i 递推，
// 每一步都是整数，避免先算阶乘再做大数除法。
void combination(ll M, ll K) {
    big[0] = 1;
    big_len = 1;
    for (ll i = 1; i <= K; i++) {
        big_mul_small(M - K + i);
        big_div_small(i);
    }
}

// 按高位到低位输出高精度数，低位段补足 9 位前导零。
void print_big() {
    printf("%lld", big[big_len - 1]);
    for (ll i = big_len - 2; i >= 0; i--) {
        printf("%09lld", big[i]);
    }
    printf("\n");
}

int main() {
    ll k, x;
    scanf("%lld %lld", &k, &x);

    // 第一步：常数项 g(x) = x^x mod 1000。
    ll g = power_mod(x, x, MOD_G);

    // 第二步：隔板法，a1+...+ak = g(x) 的正整数解组数为 C(g(x)-1, k-1)。
    combination(g - 1, k - 1);
    print_big();
    return 0;
}

复杂度

时间复杂度：
- 快速幂计算 $x^x \bmod 1000$ 的时间复杂度为 $O(\log x)$ ；
- 计算组合数 $\binom{g(x) - 1}{k - 1}$ 时， $k \leqslant 100$ ，乘除计算次数不超过 $O(k)$ 次大整数乘除，总运行时间小于 $1\text{ ms}$ 。
空间复杂度：
- 仅存储若干中间大整数与输入变量，空间复杂度为 $O(k)$ （大整数所占位数），即 $O(1)$ 常数级内存。

总结

利用快速幂计算较小模数下的幂次取模，将大输入 $x$ 迅速收缩至常数级别 $g(x) < 1000$ 。
方程正整数解组数是典型的隔板模型，结论为 $\binom{N - 1}{k - 1}$ 。
组合数结果达到上百位，采用高精度计算（Python 内置大整数天然支持）。

「一本通 6.6 练习 2」方程的解

目录

形式化题目

正解

思路

图示解析

代码

复杂度

总结