数字统计问题的暴力解法与数学优化

1. 问题分析与算法设计

1.1 问题理解与数学建模

这道题目要求我们统计数字x在1到n的所有整数中出现的总次数。看似简单，但需要仔细分析数字出现的规律。以样例n=11,x=1为例，我们需要检查每个数字的每一位：

• 1：包含1（1次）
• 10：包含1（十位1次）
• 11：包含两个1（十位和个位各1次）
• 其他数字不包含1

总和为4次，与样例输出一致。

1.2 暴力解法思路

最直观的解法是遍历1到n的每个数字，然后检查该数字的每一位是否等于x。具体步骤：

1. 初始化计数器sum=0
2. 对于i从1到n：
   a. 将i赋值给临时变量temp
   b. 当temp≠0时循环：
   i. 检查temp%10（个位数）是否等于x
   ii. 如果是，sum加1
   iii. temp除以10（去掉已检查的个位）
3. 输出sum

这个算法的时间复杂度是O(n*log₁₀n)，因为每个数字需要检查其所有位数（最多log₁₀n位）。

1.3 算法优化思考

虽然暴力解法对于n≤10⁶的数据规模已经足够（现代计算机可以在毫秒级完成），但我们可以思考更高效的数学解法。例如，可以分别计算x在每个数位上出现的次数，然后累加。这种方法的时间复杂度可以降到O(log₁₀n)，但对于编程竞赛的普及组题目，暴力解法已经足够。

2. 代码实现与细节解析

2.1 完整C++代码实现

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

int main() {
    int n, x;
    cin >> n >> x;
    
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        int temp = i;
        while (temp != 0) {
            if (temp % 10 == x) {
                sum++;
            }
            temp /= 10;
        }
    }
    cout << sum << endl;
    return 0;
}