CF1028H: Make Square
区间内选两个数,用最少乘除质数操作使乘积为完全平方;按右端点扫描,维护每个 gcd 的最大下标与答案前沿。来源 Codeforces 1028 H · 难度 Codeforces 2900 · 时间 7 s,空间 1024 MB · 标签 数学 / 数论 / 扫描线 / DP / 区间查询
题目描述
称数组 是好的,如果存在 使得 是完全平方数。
一次操作可以选择一个元素,乘以任意质数,或者除以一个能整除它的质数。记 为把数组变成好的所需最少操作次数。
给定数组 和 次询问。每次询问给出 ,求
,,,。
题解
先把每个 的平方因子去掉,记剩下的平方自由部分为 ,并令 为 的不同质因子数。两个平方自由数的乘积为完全平方数,当且仅当它们相等;把 变成相同数的最少操作数为
因此询问就是求区间内点对的最小距离。
按右端点 扫描。定义
空集取 。
加入 时,对每个 和每个 ,用 更新
然后令 。这里 遍历 的约数,也就是点对的可能公共约数;当 取到点对的 时, 就是真实距离。
对询问 ,答案为
由对 的归纳, 恰好是满足区间答案不超过 的最大左端点,因此查询公式正确。更新 必须先于 ,保证点对的两个下标不同。
复杂度
每个 至多有 个不同质因子:前 个质数的乘积已经大于 。因此至多有 个约数,答案只可能在 。
加入一个数时枚举约数和 ,查询时枚举 。时间
状态按值域开表时空间为 ,其中 ;若只存出现过的约数,则为 。
参考
- 题目链接:CF1028H Make Square