1 条题解

  • 0
    @ 2026-11-15 15:17:21

    题目分析

    考点:桶排序、初等数论。

    题目要求维护一个可插入、可删除的集合,并支持查询:最大的 kk,使得集合中存在某个数 yy 满足 yk∣xy^k \mid x(kk 可以为 00)。

    暴力做法:每次询问时枚举集合中的所有数 yy,判断 yy 是 xx 的几重约数(即不断用 yy 去除 xx,统计能除几次)。复杂度 O(nq)O(nq),适合小数据。

    优化一:注意到 ai,t,xa_i, t, x 的范围都是 10510^5,但集合中的不同数值远少于元素个数。因此用桶 cnt[v] 记录数值 vv 当前在集合中出现的次数,插入/删除只需 O(1)O(1) 修改对应桶。

    优化二:询问 xx 时不需要枚举所有数值,只需枚举 xx 的约数即可。因为若 yk∣xy^k \mid x 且 k≥1k \ge 1,则 yy 必然是 xx 的约数。枚举 xx 的所有约数(O(x)O(\sqrt x)),对每个出现在集合中的约数 yy,计算最大的 kk 使 yk∣xy^k \mid x,取最大值即可。

    计算重数:对给定的 yy,不断用 yy 去整除 xx 并计数,即为该 yy 对应的重数。注意要防止乘法溢出。

    此外题目保证 ai,t≠1a_i, t \neq 1,所以不必特殊处理 y=1y = 1 时 kk 无上限的情况。若集合为空导致 k=0k = 0,按题目要求输出 00。

    总复杂度约 O(qA)O(q\sqrt{A}),可以通过。

    • 1

    信息

    ID
    114
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    1
    已通过
    1
    上传者