AcWing3400. 统计次数

题目描述

给定两个正整数 \(n\) 和 \(k\)，求从 \(1\) 到 \(n\) 这 \(n\) 个正整数的十进制表示中 \(k\) 出现的次数。

输入格式

共一行，包含两个整数 \(n\) 和 \(k\)。

输出格式

输出一个整数，表示答案。

数据范围

\(1 \le n \le 10^6\),
\(1 \le k \le 9\)

输入样例：

    12 1

输出样例：

    5

样例解释

从 \(1\) 到 \(12\) 这些整数中包含 \(1\) 的数字有 \(1,10,11,12\)，一共出现了 \(5\) 次 \(1\)。

解题思路

\(\qquad\)看到题目看似挺复杂的，那就先从暴力的角度思考：
\(\qquad\)我们可以从\(1\)枚举到\(n\)，把每个数的每一位分解出来，然后判断是不是\(k\)就行。
\(\quad\)\(\huge 那这样的时间复杂度是怎么样的？\)
\(\qquad\quad\)我们有\(n\)次循环，每次循环内部的复杂度也就是\(log_{10}i\)，最后的复杂度总和就是\(\LARGE \sum_{i=1}^{n}log_{10}i\)
也就是\(\LARGE log_{10}\prod_{i=1}^{n}\)
也就是\(\LARGE log_{10}(n!)\)
这个复杂度是绰绰有余的，在\(desmos\)上画了下图

蓝色的是\(log_{10}(n!)\)，红色是\(nlog_{10}n\)
所以跑得过，上代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10;
int cnt[N], res;

int main() 
{
    int n, k;
    scanf("%d%d", &n, &k);
    
    for (int i = 1; i <= n; i ++ ) 
    {
        int x = i;
        while (x) 
        {
            res += (x % 10 == k);
            x /= 10;
        }
    }
    printf("%d\n", res);
    
    return 0;
}