「一本通 5.3 练习 1」数字游戏

形式化题目

给定正整数 $a, b, N$ （ $1 \leqslant a, b \leqslant 2^{31}-1$ ， $1 \leqslant N < 100$ ）。记 $S(x)$ 为 $x$ 的十进制各位数字之和，求闭区间 $[a, b]$ 中满足 $S(x) \bmod N = 0$ 的整数 $x$ 的个数。题目含多组测试数据，每组输出一行。

样例 1 19 9 要求统计 $[1, 19]$ 中数字和为 $9$ 的倍数的数，下表列出区间边界附近的判定过程：

数字 $x$	数字和 $S(x)$	$S(x) \bmod 9$	是否取模数
$8$	$8$	$8$	否
$9$	$9$	$0$	是
$10$	$1$	$1$	否
$17$	$8$	$8$	否
$18$	$1+8=9$	$0$	是
$19$	$1+9=10$	$1$	否

区间内只有 $9$ 和 $18$ 两个取模数（其余数的数字和 mod 9 均不为 0），故输出 $2$ 。

正解

思路

朴素做法与瓶颈。 最直接的想法是枚举 $x = a, a+1, \dots, b$ ，逐个拆位求和再取模。但区间长度最大 $2^{31}-1 \approx 2.1 \times 10^9$ ，每个数还要拆约 10 位，总操作量在 $10^{10}$ 量级，远超 $1000\,\text{ms}$ 。瓶颈在于枚举个数本身，所以必须让代价只与数字的位数（ $\leqslant 10$ ）和 $N$ （ $<100$ ）有关，与区间长度无关。

第一步：前缀相减。 区间计数可减，定义

f_N(x) = \bigl|\{\, 0 \leqslant y \leqslant x : S(y) \equiv 0 \pmod N \,\}\bigr| \;\Longrightarrow\; \text{ans} = f_N(b) - f_N(a-1).

$0$ 同时出现在两份计数里（ $S(0)=0$ ），相减正好抵消，剩下的恰是 $[a, b]$ 的答案。双侧约束被消成单侧的 $[0, x]$ 计数。

第二步：逐位决策只需余数。 对 $x$ 的数位 $d_0 d_1 \dots d_{L-1}$ 从高位到低位构造 $[0, x]$ 内的数，维护：当前余数 rem（已填前缀的数字和 mod $N$ ）与 tight（前缀是否贴着 $x$ 的上界——为真时本位只能填 $0 \sim d_i$ ，为假时自由填 $0 \sim 9$ ）。所有位填完后，rem == 0 即为合法数。这样设计的两个理由：

判断只发生在末尾且只看"是否为 $N$ 的倍数"，前面的和对未来的贡献等价于它对 $N$ 的余数， $N < 100$ 意味着余数只有 99 种取值，状态从"和的大小"压缩到"余数"；
已填的具体数字对未来没有任何影响——剩余位的可选范围只由 pos 和 tight 决定，目标只由 rem 决定，因此相同三元组必然返回相同值，可以记忆化。

于是得到数位 DP 的转移（ $limit$ 为本位上限）：

\text{dfs}(pos, rem, tight) = \sum_{d=0}^{limit} \text{dfs}\bigl(pos+1,\ (rem+d) \bmod N,\ tight \land d = limit\bigr),

递归出口为 $pos = L$ （所有位填完）：此时 rem == 0 就返回 1，否则返回 0。

转移过程展示。 下表把样例上界 $x = 19$ 、 $N = 9$ （digits = (1, 9)）的全部状态列出来：

状态 $(pos, rem, tight)$	展开	返回值
$(0, 0, \text{True})$	贴上界，本位只能填 $d \in \{0,1\}$ ： $d=0$ 走 $(1, 0, \text{False})$ ， $d=1$ 走 $(1, 1, \text{True})$	$2 + 1 = 3$
$(1, 0, \text{False})$	已松绑，本位自由填 $0 \sim 9$ ；要求 $d \bmod 9 = 0$ ，即 $d \in \{0, 9\}$	$2$
$(1, 1, \text{True})$	贴上界只能填 $0 \sim 9$ ；要求 $(1+d) \bmod 9 = 0$ ，只有 $d = 8$	$1$

这张表有三点值得注意：返回值 $3$ 正是 $[0, 19]$ 中的取模数 $0, 9, 18$ ；状态 $(1, 0, \text{False})$ 只依赖"当前余数"，无论它来自哪个前缀——这正是记忆化能合并重复子问题的证据；而 tight = True 的前缀在整棵搜索树里只有一条线性路径，绝大多数工作量都落在可共享的松绑状态上。最终 $f_9(19) - f_9(0) = 3 - 1 = 2$ ，与样例一致。

前导零不需要特判。 不足 $L$ 位的数等价于"高位填 0"，而 $0$ 对数字和没有贡献，合法性统一由末尾的 rem == 0 判断，因此不必像部分数位 DP 那样额外维护"是否已经开始填非零数字"。

代码

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46#!/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-09-30 20:27
# update_at: 2026-09-30 20:32

import sys
from functools import cache


def count_mod_sum(x: int, n: int) -> int:
    """[0, x] 中各位数字之和 mod n 为 0 的个数（含 0 本身）。"""
    digits = tuple(map(int, str(x)))  # 上界逐位拆开，len 最多 10

    @cache
    def dfs(pos: int, rem: int, tight: bool) -> int:
        """从高位往低位填数：前缀数字和 mod n 余 rem，当前位是否贴着上界。"""
        if pos == len(digits):  # 位数填满，只剩"数字和是否为 n 的倍数"
            return int(rem == 0)
        limit = digits[pos] if tight else 9  # 贴上界时本位最多填到上界的这一位
        return sum(
            dfs(pos + 1, (rem + d) % n, tight and d == limit)  # 放入数字 d
            for d in range(limit + 1)
        )

    return dfs(0, 0, True)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    while True:  # 多组测试数据，读到文件末尾为止
        try:
            a, b, n = next(data), next(data), next(data)
        except StopIteration:
            break
        lo, hi = (a, b) if a <= b else (b, a)  # 题面只说闭区间 [a, b]，没保证 a 在前
        # 前缀相减：0 在两份计数里各算一次正好抵消，剩下 [a, b] 的答案
        out.append(str(count_mod_sum(hi, n) - count_mod_sum(lo - 1, n)))

    print('\n'.join(out))


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/**
 * 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-05 10:46
 * update_at: 2026-10-05 10:46
 */

// 数位 DP：统计 [a, b] 中各位数字之和 mod N 为 0 的数的个数。
// 前缀相减：ans = f(b) - f(a-1)，其中 f(x) 统计 [0, x] 的合法数个数。
// 状态 (pos, rem, tight)：从高位往低位填数，rem 是已填前缀的数字和 mod N，
// tight 表示前缀是否贴着上界 x。前导零不需要特判：高位填 0 不影响数字和。

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

typedef long long ll;

const int MAXL = 12;   // 2^31-1 最多 10 位，留点余量
const int MAXN = 105;  // N < 100

ll digit[MAXL];        // digit[pos] = 上界 x 从高到低第 pos 位的数字
ll digits_tmp[MAXL];   // 拆位时的临时数组（低位在前）
ll len;                // 上界 x 的位数
ll memo[MAXL][MAXN];   // memo[pos][rem] = 松绑状态下 (pos, rem) 的答案，-1 表示未算过
ll n;                  // 本组询问的模数 N

// 从第 pos 位开始填数：前缀数字和 mod N 余 rem，tight 表示是否贴上界。
// 填完全部位数后 rem == 0 即为合法数。
ll dfs(ll pos, ll rem, bool tight) {
    if (pos == len) { // 位数全部填完，只看数字和是否为 N 的倍数
        if (rem == 0) return 1;
        return 0;
    }
    if (!tight && memo[pos][rem] != -1) return memo[pos][rem]; // 松绑状态可记忆化

    ll limit = 9; // 自由填 0..9
    if (tight) limit = digit[pos]; // 贴上界时本位最多填到上界的这一位

    ll res = 0;
    for (ll d = 0; d <= limit; d++) {
        res += dfs(pos + 1, (rem + d) % n, tight && d == limit);
    }
    if (!tight) memo[pos][rem] = res; // tight 路径每棵搜索树只有一条，不用记
    return res;
}

// 统计 [0, x] 中数字和 mod N 为 0 的个数（0 本身也算，S(0)=0）。
ll count_mod_sum(ll x) {
    if (x < 0) return 0;
    len = 0;
    while (x > 0) { // 拆位：digit[0] 是最高位
        digits_tmp[len] = x % 10;
        x /= 10;
        len++;
    }
    for (ll i = 0; i < len; i++) digit[i] = digits_tmp[len - 1 - i];
    // 只清空本组会用到的 memo 范围（N 变了必须重算）
    for (ll i = 0; i < len; i++)
        for (ll j = 0; j < n; j++)
            memo[i][j] = -1;
    return dfs(0, 0, true);
}

ll a, b;

void solve() {
    if (a > b) { ll t = a; a = b; b = t; } // 题面没保证 a 在前，保险起见交换
    // 前缀相减：0 在两份计数里各算一次正好抵消
    cout << count_mod_sum(b) - count_mod_sum(a - 1) << "\n";
}

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

    while (cin >> a >> b >> n) { // 多组测试数据，读到 EOF
        solve();
    }

    return 0;
}

复杂度

时间复杂度：状态 $(pos, rem, tight)$ 至多 $10 \times N \times 2 \leqslant 1980$ 个，每个状态枚举至多 10 个数字转移，单次 $f_N(x)$ 不超过 $2 \times 10^4$ 次递归调用；一次查询算两次前缀， 12 组询问总操作量 $10^5$ 级，与区间长度无关。本地实测真实数据 $0.021\,\text{s}$ ，远低于 $1000\,\text{ms}$ 。
空间复杂度：递归深度 $L \leqslant 10$ ，@cache 缓存 $\leqslant 1980$ 个键值对且随 count_mod_sum 返回而释放；实测峰值 $15.0\,\text{MB}$ ，远低于 $128\,\text{MB}$ 。

总结

本题是数位 DP 的入门模板，解题骨架可以迁移到一大类"统计区间内满足数位条件的数"的问题：

前缀相减： $[a, b] \to f(b) - f(a-1)$ ，把双侧区间约束消成单侧 $[0, x]$ 计数，注意 $0$ 会被两份计数各算一次、相减自动抵消；
按位记忆化：从高位到低位填数，状态只保留"会影响未来的量"——本题是 (pos, 当前数字和 mod N, 是否贴上界)，tight 负责实现上界约束，rem 负责把数字和压缩成 99 种等价类；
复杂度只与位数和 $N$ 同阶： $O(L \cdot N \cdot 10)$ ，这是相对朴素枚举 $O((b-a) \log b)$ 的根本改进；当条件换成"相邻数位差"或"含特定数位"时，只需在状态里补上对应的充分统计量。

「一本通 5.3 练习 1」数字游戏

目录

形式化题目

正解

思路

代码

复杂度

总结