[NOIP2013-普及]计数问题

题目描述

试计算在区间 $1$ 到 $n$ 的所有整数中，数字 $x$ （ $0 \leqslant x \leqslant 9$ ）共出现了多少次。注意统计的是所有出现位置：例如在 $1$ 到 $11$ 中，即在 $1,2,\dots,11$ 中，数字 $1$ 出现在 $1$ 、 $10$ 以及 $11$ 的两个数位上，共 $4$ 次。

输入格式：一行两个整数 $n, x$ ，用一个空格隔开。输出格式：一行一个整数，表示 $x$ 出现的次数。

输入样例#1：11 1，输出样例#1：4。

数据范围： $1 \leqslant n \leqslant 1{,}000{,}000$ ， $0 \leqslant x \leqslant 9$ 。

思路

数位统计： $1 \sim n$ 中 $x$ 的总次数等于它在每个数位上出现次数之和。对每个权重 $p$ ，把 $n$ 切成高位 $high$ 、当前位 $cur$ 、低位 $low$ 三段：当前位取 $0 \dots x-1$ 贡献 $high \times p$ ， $cur > x$ 再加 $p$ ， $cur = x$ 再加 $low + 1$ 。 $x = 0$ 时前缀全 0 的数并不存在，每层要减去 $p$ 做前导零修正。

参考代码

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#!/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-02 10:05
# update_at: 2026-10-02 10:05

import sys


def count_digit(n: int, x: int) -> int:
    """统计 1..n 的十进制表示中数字 x 一共出现了多少次。"""
    total = 0
    p = 1  # 当前考察的数位权重：1 是个位，10 是十位，以此类推
    while p <= n:
        # 把 n 在这一位切成三段：高位 / 当前位 / 低位
        high, cur, low = n // (p * 10), n // p % 10, n % p

        # 当前位取值小于 x：前缀只能取 0..high-1，后缀任取 0..p-1
        total += high * p
        # 当前位取值与 x 的比较决定前缀恰好取 high 时的后缀范围
        if cur > x:
            total += p          # 后缀任取 0..p-1
        elif cur == x:
            total += low + 1    # 后缀只能取 0..low，再加上数 n 自己

        if x == 0:
            total -= p          # 前导零修正：前缀全 0 的“数”并不存在，刚才多算了一整段
        p *= 10
    return total


def solve() -> None:
    """读入 n 和 x，输出 x 在 1..n 中出现的次数。"""
    n, x = map(int, sys.stdin.buffer.read().split())
    print(count_digit(n, x))


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

#include <bits/stdc++.h>

typedef long long ll;

// 统计 1..n 的十进制表示中数字 x 一共出现了多少次（数位统计）
ll count_digit(ll n, ll x) {
    ll total = 0;
    ll p = 1; // 当前考察的数位权重：1 是个位，10 是十位，以此类推
    while (p <= n) {
        // 把 n 在这一位切成三段：高位 / 当前位 / 低位
        ll high = n / (p * 10);
        ll cur = n / p % 10;
        ll low = n % p;

        // 当前位取 0..x-1：前缀只能取 0..high-1，后缀任取 0..p-1
        total += high * p;
        // 当前位与 x 的比较决定前缀恰好取 high 时的后缀范围
        if (cur > x)
            total += p;        // 后缀任取 0..p-1
        else if (cur == x)
            total += low + 1;  // 后缀只能取 0..low，数 n 自己也算在内

        if (x == 0)
            total -= p; // 前导零修正：前缀全 0 的“数”并不存在，每层恰好多算 p 个
        p *= 10;
    }
    return total;
}

int main() {
    ll n, x;
    std::cin >> n >> x;
    std::cout << count_digit(n, x) << std::endl;
    return 0;
}