1 条题解
-
0
题目分析
容易发现,在左端点固定的时候,若右端点向右移动,则区间的 值要么不变,要么至少乘以 。而对于一个质数,它不可能成为任意两个与它不等的数的 ,而第 个质数是 ,所以在所有区间的 中,那些大于 的是没有用的。
因此,记 ,则当左端点固定的时候,不同的有用 只有 个。
考虑从右向左移动左端点,并且维护以当前点为左端点的不同 。具体地,可以用两个集合 分别维护当前存在的不同 和所有可能有用的 。左端点左移到 的时候,需要将 放入 ,并遍历 中本来就存在的区间,对 取 后重新放入 。每次更新完之后,就把当前 中的元素放入 中。最后对 中的元素求 即可。
时间复杂度 。
- 1
信息
- ID
- 43
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者