给出一个长度为 n 的数列 { a[1] , a[2] , a[3] , ... , a[n] }，以及 m 组询问 ( l[i] , r[i]
, k[i])。
求数列下标区间在 [ l[i] , r[i] ] 中有多少数在该区间中的出现次数与 k[i] 互质（最大公约数为1）。
[编程题]数列互质
- 热度指数：136 时间限制：C/C++ 6秒，其他语言12秒 空间限制：C/C++ 512M，其他语言1024M
- 算法知识视频讲解
输入描述:
第一行，两个正整数 n , m (1 ≤ n, m ≤ 50000)。 第二行，n 个正整数 a[i] (1 ≤ a[i] ≤ n)描述这个数列。 接下来 m 行，每行三个正整数 l[i] , r[i] , k[i] (1 ≤ l[i] ≤ r[i] ≤ n, 1 ≤ k[i] ≤ n)，描述一次询问。
输出描述:
输出 m 行，即每次询问的答案。
示例1
输入
10 5 1 1 1 1 1 2 2 2 2 2 4 7 2 4 7 3 4 8 2 4 8 3 3 8 3
输出
0 2 1 1 0
数列互质 题目描述 给出一个长度为 n 的数列 { a[1] , a[2] , a[3] , ... , a[n] }，以及 m 组询问 ( l[i] ,r[i] , k[i])。 求数列下标区间在 [ l[i] , r[i] ] 中有多少数在该区间中的出现次数与 k[i]互质（最大公约数为1）。
展开全文
该题之理论题解，代码打炸了(wa了)，就不放了qwq后来debug出来了，统计排序后第一个询问的答案时，我把1写成i了qwq 首先，我们明显的，我们需要使用莫队算法来维护每个颜色的出现次数，设c[i]表示区间中i出现了多少次，同时我们再维护一个数组d[i]表示出现次数为i的有几个颜色。这两个数组在莫
展开全文
做法：莫队 + 根号分治
显然这题我们需要莫队来处理询问，我们用两个unordered_map<int, int> mp, cnt 来分别记录数字 的出现次数 和出现次数为 的数的个数 . 我们可以发现，出现次数如果很多，那么不同的数字就会很少；不同的数字很多，那么出现的次数就会
展开全文
问题信息
通过挑战的用户
-
2022-01-23 19:12:05 -
2021-03-25 12:53:35
-
2018-06-19 13:34:16
-
2018-06-16 20:31:33
-
2018-06-13 14:42:37
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
