【每日一题】4月6日题目精讲 枚举优化

题号 NC13221
名称 数码
来源 美团2017年CodeM大赛-资格赛
戳我进入往期每日一题汇总贴~

一切的解题其实都是从最暴力开始的，本题最暴力的方法：先枚举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

为了简化问题，我们可以先求区间[1,r]的答案然后求区间[1,l-1]的答案（这样子不用过于纠结左界的问题，不容易出错）。

观察枚举的过程你可以发现以下几点：

第一，x其实只是一个中间的渠道，我们实际上也并不关心x的值和不同的x对应的因子都有谁，我们要的只有最后的统计结果。

第二，因子都是成对出现的，即x可以表示成 的形式,其中 （完全平方数有一对a=b的情况，后面可能需要特判）。

第三，如果我们固定了 当中的a，那么x在[l,r]的范围内取值时，可以取到的b是连续的，如时，b可以取2，3。

那么我们可以考虑枚举a，计算出b的取值范围:,然后我们可以对b的最高位直接进行统计。

现在问题就变成了，给你一个区间[L,R],问这个区间中的数最高位中1～9每个数码出现的次数。

我们也来看一个例子（不要看不起这种看起来低端的操作，不会的时候尝试手算一个例子是也许会有奇效的。）

L=1，R=317
最高位是1：1，10-19，100-199，共1+10+100个数字；
最高位是2：2，20-29，200-299，共1+10+100个数字
最高位是3：3，30-39，300-317，共1+10+18个数字
最高位是4：4，40-49，共11个数字；
最高位是5：5，50-59，共11个数字；
最高位是6：6，60-69，共11个数字

由此我们可以看到我们只要是按照几位数和最高位是几进行枚举，有多少个这样的数就可以直接统计出来。
具体的操作是：先枚举是几位数num，然后枚举最高位k，这种情况下能取值的范围是区间端点相减加一就是数字个数。
如：R=2333，三位数最高位是2时：左界是200，右界是min(2333，299)=299。这样b的首位为某个数值的个数就求出来了。

而a用了多少个则更简单——就是b的取值范围。

特别注意，算出来左界大于右界的时候说明一个都取不了，直接是0个，不要再去区间端点相减加一算个数了。

但是这里其实还会有一个问题：所有小于的数你会把它当成a算一遍再当成b算一遍，然后就重了，由于有完全平方数的存在，直接除以二其实也不是个特别好的办法，所以实际上b的下界是要从a开始枚举（即保证中 ）就可以了。

算法时间复杂度：

枚举a：；

计算对应的b中最高位每个数码出现的次数:；

总复杂度：。

代码可戳我查看

看完邓老师的题解，记得自己去做题提高呀~
欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目4月13日中午12：00之前写的题解有获得牛币资格~

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴