首页 > 试题广场 >

数码

[编程题]数码
  • 热度指数：887 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给定两个整数 l 和 r ，对于所有满足1 ≤ l ≤ x ≤ r ≤ 10^9 的 x ，把 x 的所有约数全部写下来。对于每个写下来的数，只保留最高位的那个数码。求1～9每个数码出现的次数。

输入描述:
一行，两个整数 l 和 r (1 ≤ l ≤ r ≤ 10^9)。


输出描述:
输出9行。

第 i 行，输出数码 i 出现的次数。
示例1

输入

1 4

输出

4
2
1
1
0
0
0
0
0
算法知识视频讲解
开通博客
头像 WA_TLE
发表于 2020-04-05 16:57:46
题解： 菜鸟讲解版 很明显的数论分块。等等，什么是数论分块？？？懂数论分块的直接跳过以下一部分。以下所有分式除法均为整除。----------分割线数论分块，顾名思义，将一段连续的区间分成一块一块相同的区间。简单点，将[1,n]这段区间来分块，分成，,,。k个块。属于同一个块之间的元素满足。好了，我 展开全文
去ta的博客 赞 (21) 回复(2) 收起
头像 精神病科黄主任
发表于 2020-04-03 19:59:02
思路：求l到r的个数 转换为求1到r的个数 减去 1到l-1的个数可以看到 l和r的长度长达1e9 如果暴力算每个的话 光是枚举x就要1e9可能会想到枚举约数，但是这样也还不够，复杂度还是高的批爆枚举约数是肯定没错的，问题是考虑如何去优化可以考虑去枚举以x为最高位的 区间的约数的个数比如求最高数码x 展开全文
去ta的博客 赞 (15) 回复(2) 收起
头像 Kur1su
发表于 2020-04-06 10:01:12
Solution Code #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long long LL; const int N = 1 展开全文
去ta的博客 赞 (9) 回复(0) 收起
头像 O__0
发表于 2020-04-05 12:03:18
首先，对于求区间 [l, r] 的问题，可以转换成求 [1, r] 的问题。答案为 [1, r] 的结果减去 [1, l - 1] 的结果。然后，需要分别统计最高位数字不同的约数的出现的次数，我们可以转变思路，枚举约数，统计每个约数在区间中出现的次数。假设这道题没有区分最高位，只是求约数个数，那就是 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 wxyww
发表于 2020-04-06 10:34:38
solution 首先利用前缀和思想，用的答案减去的答案就是的答案。 所以现在我们只需要考虑如何求出中每个数码在所有数字的约数中出现的次数即可。 然后是非常经典的将计算每个数字的约数改为枚举约数计算该约数的倍数有多少个。暴力做就是。这样复杂度是无法通过此题。 看到上面式子可以数论分块，所以直接套一个 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 吴国庆
发表于 2020-04-04 21:13:41
题目描述 给定两个整数 l 和 r ，对于所有满足1 ≤ l ≤ x ≤ r ≤ 10^9 的 x ，把 x 的所有约数全部写下来。对于每个写下来的数，只保留最高位的那个数码。求1～9每个数码出现的次数。 题解 首先问题可以转化为solve(r)-solve(l-1)的形式那么考虑如何求1~x中满 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 塞蒙尘
发表于 2020-04-03 21:12:41
Description 给定两个整数 和 ，对于所有满足 的 ，把 的所有约数全部写下来。对于每个写下来的数，只保留最高位的那个数码。求每个数码出现的次数。 Solution 一个很显然的思路是，枚举以开头的数，计算它的倍数在中出现的次数。我们设为的倍数在中出现的次数，那么有故而的倍数在中出 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 LB_tq
发表于 2020-04-05 23:03:00
Solution 数论分块，就是利用一段区间内的数整除同一个数结果相同的性质减少运算量的技巧。 回到题目，要求区间 内的答案。已知的是 内数 当做约数的次数为 ，所以问题可以转化为区间 与区间 的答案之差。 暴力计算的话，时间复杂度是 的，不能承受。所以使用数论分块来减少计算量：由于整 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 shyyhs
发表于 2020-04-09 17:17:11
题目要求区间[l,r]的每个数的因数,然后计算每个因数最高的数是出现多少次？那咋写呢?考虑朴素算法..就是枚举[l,r]每个数的因子再对最高位进行统计..但是这样算法的复杂度就到了大于O(r-l)的级别.具体我也不会算.这样肯定不行,考虑优化.怎么优化呢?首先求[l,r]中区间每个因数最高的数是出现 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 luo想要个气球
发表于 2020-04-06 09:36:57
首先把【L ， R】的问题转化成【1 , R】-【1 , L-1】，因为想要求1 ~ n中有几个数约数有x，可以通过n/x求得；然后对于每个数码1,2,3....分别求，以1为例： 求1 ~ n中约数数码为1的，应该要求这样的一些区间【1,1】、【10,19】、【100,199】【1000,1999 展开全文
去ta的博客 赞 (2) 回复(0) 收起

问题信息

C++工程师 golang工程师 2017 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 c#工程师 美团 测试开发工程师 数学 大数据开发工程师 Java工程师
来自：CodeM 2017美...
难度：
5条回答 5363浏览

热门推荐

通过挑战的用户

相关试题

数码

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号