【枚举优化】理论ac题解-数码

一点说明

是的，你现在看到的是一个理论ac选手的题解，换句话说，本人并没有写过这个题的代码，只是靠嘴ac，但我会尽我所能把这个题的从一头雾水到找到解法的可能的思路说清楚，如果你觉得没ac不配写题解请点叉（其实我也觉得的自己没ac写题解怪怪的，但是实在是时间有限，为了多贡献出一点题解就这样吧）。如果有什么bug欢迎大家指正，如果有什么疑问也欢迎提出一起探讨哇！

题目描述

给定两个整数 l 和 r ，对于所有满足1 ≤ l ≤ x ≤ r ≤ 10^9 的 x ，把 x 的所有约数全部写下来。对于每个写下来的数，只保留最高位的那个数码。求1～9每个数码出现的次数。(1 ≤ l ≤ r ≤ 10^9)。

思路

一切的解题其实都是从最暴力开始的，本题最暴力的方法：枚举x，然后枚举x的因子，将最高位的情况进行统计。
eg:l=3 r=6:
x=3 因子有1 3
x=4 因子有1 2 4
x=5 因子有1 5
x=6 因子有1 2 3 6
观察枚举的过程你可以发现以下几点：
第一，x其实只是一个中间的渠道，我们实际上也并不关心x的值，和不同的x对应的因子都有谁，我们要的只有最后的统计结果。
第二：因子都是成对出现的，即x可以表示成)的形式,其中（完全平方数有一对a=b的情况，可能需要特判）
第三，如果我们固定了)当中的a，那么x在[l,r]的范围内取值时，可以取到的b是连续的，如时，b可以取2，3
那么我们可以考虑枚举a，计算出b的取值范围:,然后我们可以对b的最高位直接进行统计。
现在问题就变成了，给你一个区间[L,R],问这个区间中的数最高位中1～9每个数码出现的次数。
我们也来看一个例子（不要看不起这种看起来低端的操作，不会的时候尝试手算一个例子也许会有奇效。）
L=22，R=317
最高位是1：100-199，共100个数字；
最高位是2：22-29，200-299，共8+100个数字
最高位是3：30-39，300-317，共10+18个数字
最高位是4：40-49，共10个数字；
最高位是5：50-59，共10个数字；
最高位是6：60-69，共10个数字；
……
由此我们可以看到我们只要按照几位数和最高位进行枚举，有多少个这样的数可以直接统计出来。
具体的操作是：先枚举是几位数num，然后枚举最高位k，这种情况下能取值的范围是。区间端点相减加一就是数字个数。
如：L=233，R=2333，三位数最高位是2时：左界是max(233,200) = 233,右界是min(2333，299)=299。
特别注意，算出来左界大于右界的时候说明一个都取不了，直接是0个，不要再去区间端点相减加一算个数了。
还有一个可能出bug的细节是前面没提到的：如果b的范围里面包含了a,即a*a这种情况在题目的范围里，这个时候这个a会被算两遍，记得剪掉。
算法时间复杂度：
枚举a：；
计算对应的b中最高位每个数码出现的次数:)（9:枚举1到9，是b的位数）。
总复杂度：。