数字统计

题目描述

统计区间 $[L,R]$ 内所有整数中数字 2 出现的次数。输入一行两个正整数 $L,R$ ；输出一行一个整数表示次数。样例输入：2 22，样例输出：6。

思路

把区间和写成前缀函数之差 $F(R)-F(L-1)$ 。设 $x=10q+r$ ，按个位分块得 $F(x)=10F(q-1)+q+(r+1)c(q)+[r\ge2]$ ，其中 $c(q)$ 为 $q$ 中数字 2 的个数。递归深度为位数，用 map 记忆化。

参考代码

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#!/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-29 18:40
# update_at: 2026-09-29 18:40

import sys
from functools import cache

TARGET = "2"  # 题目要统计的目标数字；用字符串形式是为了配合 str.count


@cache
def count_upto(x: int) -> int:
    """统计 1..x 中数字 2 出现的总次数；区间答案用 count_upto(right) - count_upto(left - 1)。"""
    if x < 2:
        return 0
    quotient, remainder = divmod(x, 10)
    if quotient == 0:
        return 1  # 个位数：只有 2 本身算一个

    # 把 0..x 按"高位 + 个位"拆开，逐块统计（x = 10 * quotient + remainder）
    blocks = 10 * count_upto(quotient - 1)  # 高位取 0..quotient-1 时，高位里的 2 被 10 个低位各复制一遍
    tail_low = quotient                     # 这些完整块里，个位每个数字都恰好出现 quotient 次
    tail_high = (remainder + 1) * str(quotient).count(TARGET)  # 高位固定在 quotient，低位有 remainder+1 种
    ones_place = remainder >= 2             # 个位从 0 走到 remainder，只有 2 落在这段里

    return blocks + tail_low + tail_high + ones_place


def solve() -> None:
    left, right = map(int, sys.stdin.buffer.read().split())
    print(count_upto(right) - count_upto(left - 1))


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

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

typedef long long ll;

ll L, R;                         // 区间左右端点
map<ll, ll> memo;                // 记忆化 F(x)：1..x 中数字 2 出现的总次数

// 计算正整数 n 的十进制写法中数字 2 出现的次数
ll count_two(ll n) {
    ll cnt = 0;
    while (n > 0) {
        if (n % 10 == 2) cnt++;
        n /= 10;
    }
    return cnt;
}

// F(x)：统计 1..x 中数字 2 出现的总次数；区间答案用 F(R) - F(L-1)
ll count_upto(ll x) {
    if (x < 2) return 0;
    if (memo.count(x)) return memo[x];

    ll q = x / 10;               // 商：代表高位
    ll r = x % 10;               // 余数：代表个位

    // 一位数直接返回 1（2..9 都只有 1 个 2）
    if (q == 0) return memo[x] = 1;

    // 按个位分块：完整块贡献 10*F(q-1)+q，残块贡献 (r+1)*count_two(q)+[r>=2]
    ll res = 10 * count_upto(q - 1) + q
           + (r + 1) * count_two(q) + (r >= 2 ? 1 : 0);

    return memo[x] = res;
}

int main() {
    scanf("%lld %lld", &L, &R);
    printf("%lld\n", count_upto(R) - count_upto(L - 1));
    return 0;
}

目录

题目描述

思路

参考代码