题解： 菜鸟讲解版 很明显的数论分块。等等，什么是数论分块？？？懂数论分块的直接跳过以下一部分。以下所有分式除法均为整除。----------分割线数论分块，顾名思义，将一段连续的区间分成一块一块相同的区间。简单点，将[1,n]这段区间来分块，分成，,,。k个块。属于同一个块之间的元素满足。好了，我
展开全文
思路：求l到r的个数 转换为求1到r的个数 减去 1到l-1的个数可以看到 l和r的长度长达1e9 如果暴力算每个的话 光是枚举x就要1e9可能会想到枚举约数，但是这样也还不够，复杂度还是高的批爆枚举约数是肯定没错的，问题是考虑如何去优化可以考虑去枚举以x为最高位的 区间的约数的个数比如求最高数码x
展开全文
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
展开全文
首先，对于求区间 [l, r] 的问题，可以转换成求 [1, r] 的问题。答案为 [1, r] 的结果减去 [1, l - 1] 的结果。然后，需要分别统计最高位数字不同的约数的出现的次数，我们可以转变思路，枚举约数，统计每个约数在区间中出现的次数。假设这道题没有区分最高位，只是求约数个数，那就是
展开全文
solution 首先利用前缀和思想，用的答案减去的答案就是的答案。 所以现在我们只需要考虑如何求出中每个数码在所有数字的约数中出现的次数即可。 然后是非常经典的将计算每个数字的约数改为枚举约数计算该约数的倍数有多少个。暴力做就是。这样复杂度是无法通过此题。 看到上面式子可以数论分块，所以直接套一个
展开全文
题目描述 给定两个整数 l 和 r ，对于所有满足1 ≤ l ≤ x ≤ r ≤ 10^9 的 x ，把 x 的所有约数全部写下来。对于每个写下来的数，只保留最高位的那个数码。求1～9每个数码出现的次数。 题解 首先问题可以转化为solve(r)-solve(l-1)的形式那么考虑如何求1~x中满
展开全文
Description 给定两个整数 和 ，对于所有满足 的 ，把 的所有约数全部写下来。对于每个写下来的数，只保留最高位的那个数码。求每个数码出现的次数。 Solution 一个很显然的思路是，枚举以开头的数，计算它的倍数在中出现的次数。我们设为的倍数在中出现的次数，那么有故而的倍数在中出
展开全文
Solution 数论分块，就是利用一段区间内的数整除同一个数结果相同的性质减少运算量的技巧。 回到题目，要求区间 内的答案。已知的是 内数 当做约数的次数为 ，所以问题可以转化为区间 与区间 的答案之差。 暴力计算的话，时间复杂度是 的，不能承受。所以使用数论分块来减少计算量：由于整
展开全文
题目要求区间[l,r]的每个数的因数,然后计算每个因数最高的数是出现多少次？那咋写呢?考虑朴素算法..就是枚举[l,r]每个数的因子再对最高位进行统计..但是这样算法的复杂度就到了大于O(r-l)的级别.具体我也不会算.这样肯定不行,考虑优化.怎么优化呢?首先求[l,r]中区间每个因数最高的数是出现
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
