「一本通 5.3 练习 4」数字计数

题目描述

给定正整数 $a,b$ （ $1 \le a \le b \le 10^{12}$ ），统计区间 $[a,b]$ 中每个整数十进制表示里数码 $0\sim9$ 各出现多少次，顺序输出。输入一行两个整数 $a,b$ ；输出一行 $10$ 个整数。样例：输入 1 99，输出 9 20 20 20 20 20 20 20 20 20。

思路

用 $F(n)$ 表示 $1\sim n$ 中各数码出现次数，答案为 $F(b)-F(a-1)$ ；对每位按 $high,cur,low$ 三段直接计算闭式贡献，统计 $0$ 时跳过前导零。

参考代码

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#!/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:39
# update_at: 2026-09-30 20:39

import sys


def count_digits(n: int) -> list[int]:
    """统计 1..n 中每个数码出现的次数（n<=0 时全为 0），0 只统计真实数位上的。"""
    cnt = [0] * 10
    factor = 1                      # 当前数位的位权：1 个位、10 十位、100 百位……
    while factor <= n:
        high, cur, low = n // (factor * 10), n // factor % 10, n % factor

        # 1~9：按"当前位的数码 d 与 cur 的大小关系"把 [1,n] 分成三段计数
        for d in range(1, 10):
            if d < cur:
                cnt[d] += (high + 1) * factor    # 前缀 0..high 都能取满
            elif d == cur:
                cnt[d] += high * factor + low + 1  # 等值前缀只取到 low
            else:
                cnt[d] += high * factor          # 前缀只能取 0..high-1

        # 0：前缀不能为 0，否则该位是前导零、不是真实数位
        if cur:
            cnt[0] += high * factor              # 当前位非 0，后缀可取满 factor 个
        else:
            cnt[0] += (high - 1) * factor + low + 1  # cur==0 时 high 至少为 1
        factor *= 10
    return cnt


def solve() -> None:
    a, b = map(int, sys.stdin.buffer.read().split())
    # 区间计数用前缀和相减：[a,b] = [1,b] - [1,a-1]
    hi, lo = count_digits(b), count_digits(a - 1)
    print(' '.join(str(x - y) for x, y in zip(hi, lo)))


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/**
 * 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:55
 * update_at: 2026-10-06 00:55
 */

#include <cstdio>
#include <iostream>
using namespace std;

typedef long long ll;

ll cnt[10]; // 1~n 中每个数码出现次数

// 计算 1~n 中各数码出现次数，结果存入全局 cnt[]
void count_up_to(ll n) {
    for (int i = 0; i < 10; ++i) cnt[i] = 0;
    if (n <= 0) return;
    for (ll w = 1; w <= n; w *= 10) {
        ll high = n / (w * 10);
        ll cur = (n / w) % 10;
        ll low = n % w;
        // 数码 1~9：当前位直接按 high、cur、low 分三段计算
        for (int d = 1; d <= 9; ++d) {
            if (d < cur) cnt[d] += (high + 1) * w;
            else if (d == cur) cnt[d] += high * w + low + 1;
            else cnt[d] += high * w;
        }
        // 数码 0：跳过前导零，高位前缀从 1 开始
        if (cur == 0) cnt[0] += (high - 1) * w + low + 1;
        else cnt[0] += high * w;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll a, b;
    if (!(cin >> a >> b)) return 0;
    ll ans[10];
    count_up_to(b);
    for (int i = 0; i < 10; ++i) ans[i] = cnt[i];
    count_up_to(a - 1);
    for (int i = 0; i < 10; ++i) {
        ans[i] -= cnt[i];
        if (i) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';
    return 0;
}

「一本通 5.3 练习 4」数字计数

目录

题目描述

思路

参考代码