1、为什么不能用暴力解？
数据范围太大了，\(0<a,b<100000000\)
两个数字\(a-b\)之间，最多就有\(1^8\)个数字，每个\(10^8\)数，需要遍历每一位，就是一个数字需要遍历8次最多。
那就一次的时间复杂度最高就是:$10^8 * 8 $,而且有多组测试数据,不出意外会TLE。
2、按小学数奥问题分析
如计算 78501 中 "5" 出现的次数。 [答案：41502]
我们可以枚举“5”出现的位置，
1、如当“5”位于倒数第1位时，写成 xxxx5，由于5大于1(当前数位1小于目标值5)，前面只能取0~7849(共7850个)；
2、如当“5”位于倒数第2位时，写成xxx5x，由于5大于0(当前数位0小于目标值5)，前面只能取0~784(共785个)，后面无限制为10； 总计:7850个
3、如当“5”位于倒数第3位时，写成xx5xx，由于5等于5(当前数位5等于目标值5)，前面取0~77乘以后面无限制的100，共7800个；加上,前面取78，后面取“01”；因为还有"00",所以还需要加上一个1 ,总计：7802个。
4、如当“5”位于倒数第4位时，写成 x5xxx，由于5小于8(当前数位8大于目标值5)，前面可取0~7(共8个)，后面无限制的1000. 总计：8000个
5、如当“5”位于倒数第5位时，写成 5xxxx，由于5小于7(当前数位7大于目标值5)，后面无限制的10000. 总计：10000个
总之，枚举x出现的位置，按x与n在该位上的大小关系，分为大于、小于、等于三类讨论。
加在一起： 7850+7850+7802+8000+10000=41502
ll count_x(ll n, ll x) {
ll res = 0, tmp = 1;
ll tmp_n = n; //n的副本，因为下面是以n为运算的基础，一路除下去的，如果我们想要得到原始的n，就找不到了，这里给它照了一个像
while (n) { //从后向前一位一位的讨论
//代码中注释掉的两行，用于跟踪调试程序的分步运行情况
//int t = res;
if (n % 10 < x) res += n / 10 * tmp; //小于 n/10代表当前位数前面的数字值，比如785,tmp是指需要乘以10的几次方
else if (n % 10 == x) res += n / 10 * tmp + (tmp_n % tmp + 1); //等于 等于最麻烦，需要再次分情况讨论
else res += (n / 10 + 1) * tmp; //大于 这个加1，是因为是0~77，共78个
n /= 10; //进入前一位
tmp *= 10; //计算需要乘几个10的变量
//cout << res - t << endl;
}
return res;
}
3、对于0这个东东比较讨厌，需要单独讨论一下
（1）因为0不能当首位
就是上面讨论中提到的什么07,07849 啊，都不能从0开始，那样的话，前面就成了存在前导0了。
（2）在每一位判断时，不存在比0小的数字。
只需要分成两类，不可能存在当前位小于0的情况，只讨论等于和大于。
ll count_0(ll n) {
ll res = 0, tmp = 1;
ll tmp_n = n;
while (n) {
//代码中注释掉的两行，用于跟踪调试程序的分步运行情况
//int t = res;
if (n % 10 == 0) res += (n / 10 - 1) * tmp + (tmp_n % tmp + 1); //等于,剔除了大于0的情况
else res += (n / 10) * tmp; //大于,剔除了大于0的情况
n /= 10; //进入前一位
tmp *= 10; //计算需要乘几个10的变量
//cout << res - t << endl;
}
return res;
}
4、写一个最笨的计算办法，与用数学方法计算出来的结果进行对比，验证一下思路的正确性
//数位分离之原始版本[笨蛋版本，慢，但绝对准确，用于算法对比判断正确性]
ll stupidCount(int n, int x) {
ll res = 0;
for (int i = 1; i <= n; ++i) {
int tmp = i;
while (tmp) {
int t = tmp % 10;
if (t == x) res++;
tmp /= 10;
}
}
return res;
}
验证办法：
int n = 78501;
printf("%d ", stupidCount(n, 5));
printf("%d ", stupidCount(n, 0));
5、要的是区间段，我们算的是从1到n,怎么办呢？
现在的题目要求我们求出\([a,b]\)之间 \([0-9]\)出现的次数，这不太好求，如果我们有一个函数，可以计算出\([1-n]\)之间\(x\)出现的次数，就可以使用类似于前缀和的思想，计算出来，比如：
\(f[a,b]=count(b,x)-count(a-1,x)\)
6、测试对拍的程序
int n = 78501;
printf("%lld ", count_0(n));
for (int i = 1; i <= 9; i++) printf("%lld ", count_x(n, i));
printf("\n");
for (int i = 0; i <= 9; i++) printf("%lld ", stupidCount(n, i));
//printf("%lld ", count_x(n,5));
//printf("%d ", stupidCount(n, 5));
7、完整C++ 代码
#include <iostream>
using namespace std;
typedef long long ll;
ll count_x(ll n, ll x) {
ll res = 0, tmp = 1;
ll tmp_n = n; //n的副本，因为下面是以n为运算的基础，一路除下去的，如果我们想要得到原始的n，就找不到了，这里给它照了一个像
while (n) { //从后向前一位一位的讨论
//代码中注释掉的两行，用于跟踪调试程序的分步运行情况
//int t = res;
if (n % 10 < x) res += n / 10 * tmp; //小于 n/10代表当前位数前面的数字值，比如785,tmp是指需要乘以10的几次方
else if (n % 10 == x) res += n / 10 * tmp + (tmp_n % tmp + 1); //等于 等于最麻烦，需要再次分情况讨论
else res += (n / 10 + 1) * tmp; //大于 这个加1，是因为是0~77，共78个
n /= 10; //进入前一位
tmp *= 10; //计算需要乘几个10的变量
//cout << res - t << endl;
}
return res;
}
/**
对于0，稍作修改，
此时只需分成两类，因为不存在当前为小于0的情况，不过每次的最高为要排除全0的情况。
*/
ll count_0(ll n) {
ll res = 0, tmp = 1;
ll tmp_n = n;
while (n) {
//代码中注释掉的两行，用于跟踪调试程序的分步运行情况
//int t = res;
if (n % 10 == 0) res += (n / 10 - 1) * tmp + (tmp_n % tmp + 1); //等于,剔除了大于0的情况
else res += (n / 10) * tmp; //大于,剔除了大于0的情况
n /= 10; //进入前一位
tmp *= 10; //计算需要乘几个10的变量
//cout << res - t << endl;
}
return res;
}
int main() {
int a, b;
while (cin >> a >> b, a) {
if (a > b) swap(a, b);
cout << count_0(b) - count_0(a - 1) << ' ';
for (int i = 1; i <= 9; i++)
cout << count_x(b, i) - count_x(a - 1, i) << ' ';
cout << endl;
}
return 0;
}