数字统计问题：暴力枚举与数学规律解法详解

1. 题目背景与需求分析

洛谷P1980是一道来自NOIP2013普及组的经典计数问题。题目要求统计在1到n的所有整数中，数字x（0≤x≤9）出现的次数。这类问题在编程竞赛中非常常见，考察选手对数字处理、循环控制和边界条件的把握能力。

实际应用场景包括：

• 数据分析中的数字频率统计
• 密码学中的数字分布研究
• 商业统计中的销售数字分析

注意：题目中n的范围是1≤n≤1,000,000，这意味着算法的时间复杂度必须控制在O(n)以内，否则会因数据量过大导致超时。

2. 解题思路解析

2.1 暴力枚举法（基础解法）

最直观的解法是遍历1到n的每个数字，然后逐位检查是否等于x：

cpp复制int count = 0;
for (int i = 1; i <= n; i++) {
    int num = i;
    while (num > 0) {
        if (num % 10 == x) count++;
        num /= 10;
    }
}

时间复杂度分析：

• 外层循环n次
• 内层循环取决于数字位数，最大为7次（1,000,000是7位数）
• 总体复杂度O(7n)，在n=1e6时约7e6次操作，可以接受

2.2 数学规律法（优化解法）

更高效的解法是利用数字的数学规律，逐位计算x在每个数位上出现的次数。这种方法的时间复杂度是O(logn)，适合处理更大的n值。

核心思路：

1. 将数字拆分为个位、十位、百位等
2. 对每一位，计算x在该位上出现的次数
3. 累加所有位上的出现次数

3. 完整代码实现与注释

3.1 暴力解法实现

cpp复制#include <iostream>
using namespace std;

int main() {
    int n, x;
    cin >> n >> x;
    
    int count = 0;
    for (int i = 1; i <= n; i++) {
        int num = i;
        while (num > 0) {
            if (num % 10 == x) count++;
            num /=