数1的个数

题目描述

给定一个十进制正整数 $n$ （ $1 \leqslant n \leqslant 10000$ ），写下从 $1$ 到 $n$ 的所有整数，数一数其中出现的数字 “1” 的个数。例如 $n=12$ 时，写下 $1,2,\dots,12$ ，共出现了 $5$ 个 “1”。

输入：正整数 $n$ 。输出：一个正整数，即 “1” 的个数。

样例输入：

text

样例输出：

text

思路

$n$ 不超过 $10^4$ ，直接从 $1$ 到 $n$ 枚举每个整数，对每个数不断除以 $10$ 取余数，统计个位为 $1$ 的次数后累加即可。总时间约 $O(n \cdot d)$ （ $d \leqslant 5$ 为位数），空间 $O(1)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20#!/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-05-22 19:17
# update_at: 2026-10-04 09:30

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)  # 题面的位置量 n，先命名再参与计算
    # 把 1..n 每个整数转成字符串，累计其中 '1' 的出现次数
    ans = sum(str(i).count("1") for i in range(1, n + 1))
    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/**
 * 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 00:59
 * update_at: 2026-10-05 01:00
 */
#include <cstdio>

typedef long long ll;

ll n;   // 题目给出的上界
ll ans; // 1..n 中数字 "1" 的总个数

int main() {
    scanf("%lld", &n);
    // 枚举 1..n 的每个整数，逐位统计数字 "1"
    for (ll i = 1; i <= n; ++i) {
        ll x = i;
        while (x > 0) {
            if (x % 10 == 1) // 当前个位是 1
                ++ans;
            x /= 10;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

目录

题目描述

思路

参考代码