数列互质 题目描述 给出一个长度为 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 来分别记录数字 的出现次数 和出现次数为 的数的个数 . 我们可以发现，出现次数如果很多，那么不同的数字就会很少；不同的数字很多，那么出现的次数就会
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
