1 条题解

  • 0
    @ 2026-11-15 13:06:26

    题目分析

    容易发现,在左端点固定的时候,若右端点向右移动,则区间的 lcm \text{lcm} 值要么不变,要么至少乘以 22。而对于一个质数,它不可能成为任意两个与它不等的数的 lcm \text{lcm} ,而第 3×105+1 3 \times 10^5 + 1 个质数是 42562334256233,所以在所有区间的 lcm \text{lcm} 中,那些大于 42562334256233 的是没有用的。

    因此,记 V=4256233 V = 4256233 ,则当左端点固定的时候,不同的有用 lcm \text{lcm} 只有 log⁡V \log V 个。

    考虑从右向左移动左端点,并且维护以当前点为左端点的不同 lcm \text{lcm} 。具体地,可以用两个集合 A,B A, B 分别维护当前存在的不同 lcm \text{lcm} 和所有可能有用的 lcm \text{lcm} 。左端点左移到 i i 的时候,需要将 ai a_i 放入 A A ,并遍历 A A 中本来就存在的区间,对 ai a_i 取 lcm \text{lcm} 后重新放入 A A 。每次更新完之后,就把当前 A A 中的元素放入 B B 中。最后对 B B 中的元素求 mex \text{mex} 即可。

    时间复杂度 O(nlog⁡2V)O(n \log^2 V)。

    • 1

    信息

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