解法一：暴力枚举 O(nlogn)

遍历从 1 到 n 的每一个数字，对每个数字再检查它的每一位是否等于 x，统计总共出现的次数。(代码略）

解法二：数位统计算法 O(logn)

为了逐位计算当前十进制位k可能出现的目标数x的次数，我们将当前数分为三个部分：

  • higher: 当前位左边的数字
  • current: 当前位上的数字
  • lower: 当前位右边的数字

例如，n=1324, k=10时，十位左侧的数 `13` 记为 higher, 右侧的数 `4` 记为 lower, 十位本身 `2` 记为 current.

首先计算高位带来的贡献, 因为高位在[0, higher)取值时，

current 是一定可以取到 x 的，所以依据排列组合：

总出现次数 = len([0,higher)) * lower的所有可能情况数 = higher * k

然后计算本位贡献(就是高位取higher时的情况)分类如下：

  • 如果 current > x：当前位上 x 可以完整出现 k 次
  • 如果 current == x：当前位上 x 出现了 lower + 1 次
  • 如果 current < x：当前位上 x 不会出现额外次数

此外，当 x == 0 时高位贡献需要特殊处理，因为不能有前导零。

最后, 将高位贡献与本位贡献累加就得到了当前位出现x的所有情况数 ^_^

use std::io::stdin;

fn count (n: u32, x: u32) -> u32 {
    let mut cnt = 0;
    let mut k = 1; // 当前位数(个、十、百......)
    while k <= n {
        let current = n / k % 10;
        let lower = n % k;
        let higher = n / k / 10;

        // 高位贡献
        cnt += higher * k;
        // 本位贡献(无制约)
        if current > x {cnt += k;}
        // 本位贡献(受制于低位)
        else if current == x {cnt += lower + 1;}
        // 特判x为0(计算高位贡献时，高位不能全为0)
        if x == 0  {cnt -= k;}

        k *= 10;
    }
    cnt
}

fn main() {
    let mut line = String::new();
    stdin().read_line(&mut line).unwrap();
    let nums: Vec<u32> = line.trim().split_whitespace().map(|x| x.parse().unwrap()).collect();
    println!("{}", count(nums[0], nums[1]));
}