1 条题解
-
0
题目分析
考点:桶排序、初等数论。
题目要求维护一个可插入、可删除的集合,并支持查询:最大的 ,使得集合中存在某个数 满足 ( 可以为 )。
暴力做法:每次询问时枚举集合中的所有数 ,判断 是 的几重约数(即不断用 去除 ,统计能除几次)。复杂度 ,适合小数据。
优化一:注意到 的范围都是 ,但集合中的不同数值远少于元素个数。因此用桶
cnt[v]记录数值 当前在集合中出现的次数,插入/删除只需 修改对应桶。优化二:询问 时不需要枚举所有数值,只需枚举 的约数即可。因为若 且 ,则 必然是 的约数。枚举 的所有约数(),对每个出现在集合中的约数 ,计算最大的 使 ,取最大值即可。
计算重数:对给定的 ,不断用 去整除 并计数,即为该 对应的重数。注意要防止乘法溢出。
此外题目保证 ,所以不必特殊处理 时 无上限的情况。若集合为空导致 ,按题目要求输出 。
总复杂度约 ,可以通过。
- 1
信息
- ID
- 114
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者