给定两个正整数 n 和 k，求从 1到 n 这 n个正整数的十进制表示中 k 出现的次数。 输入格式 共一行，包含两个整数 n和 k。 输出格式 输出一个整数，表示答案。

算法1

暴力枚举每个数字的每一位，统计k出现的次数，时间复杂度为O(n*log_10(n))。

时间复杂度

参考文献

Python 代码

C++ 代码

算法2

统计k在每个数位上出现的次数，并累加得到最终答案。以k=3为例，假设当前处理的是x，x的第i位为di。有以下三种情况：

- di>k，则di可以取0~9中任意一个数字，共10^(i-1)种情况，其中i表示第i位，10^(i-1)表示该数位前(i-1)位共有10^(i-1)种情况。
- di<k，则第i位只能取0~di-1中的数字，如果i=1，则0不能出现，共di*(10^(i-1))种情况。
- di=k，则第i位只能取0~di-1中的数字，共(dk-1)*(10^(i-1)) + x%(10^(i-1))+1种情况，其中x%(10^(i-1))表示当前数位前(i-1)位的数字共有x%(10^(i-1))+1种情况，因为x前(i-1)位的数字可以取0~(x%(10^(i-1)))。

注意到以上三种情况中第一种情况和第二种情况可以合并成一个公式，故最终的公式为：

ans = ∑i=1 ^ len(n)[(n // (10^i))*10^(i-1)+min(max(n%(10^i)−k+1,0),10^(i−1))−(k==0)*10^(i−1)]
其中，n // (10^i)表示取n的前i位数字，max(n%(10^i)−k+1,0)表示取n的第i位数字时，能取到的范围。注意当k=0时，第二项需要减去10^(i-1)。

时间复杂度

参考文献

Python 代码

C++ 代码

算法3

对于每一位数位上出现k的次数进行统计。根据数位的不同分类具体处理，具体如下：

- 如果k=0，则枚举当前数位，次数为n/10^(i+1)*10^i，表示高位上数位1~n/10^(i+1)共可以变化10^i种，其中i表示数位从右数第x位，不包含本位（假设最低位为第0位）上的前缀0。

Python 代码

C++ 代码

- 如果当前位数字是k，则统计方式分为三种：

- 如果该位数字为0，则次数为前面数位（不包括本身）0~n/10^(i+1)的个数
- 如果该位数字不为0，则次数为前面数位（不包括本身）0~n/10^(i+1)的个数+1
- 如果i=0,即当前位为最低位且为k，则次数为1

Python 代码

C++ 代码

- 如果当前位数字小于k，则次数为前面数位（不包括本身）0~n/10^(i+1)的个数
- 如果当前位数字大于k，则次数为前面数位（不包括本身）0~n/10^(i+1)的个数+1
于是有以下代码

时间复杂度

参考文献

Python 代码

C++ 代码