CF1028H: Make Square

区间内选两个数,用最少乘除质数操作使乘积为完全平方;按右端点扫描,维护每个 gcd 的最大下标与答案前沿。

来源 Codeforces 1028 H · 难度 Codeforces 2900 · 时间 7 s,空间 1024 MB · 标签 数学 / 数论 / 扫描线 / DP / 区间查询

题目描述

称数组 𝑏1,…,𝑏𝑚 是好的,如果存在 𝑖<𝑗 使得 𝑏𝑖𝑏𝑗 是完全平方数。

一次操作可以选择一个元素,乘以任意质数,或者除以一个能整除它的质数。记 𝑓(𝑏1,…,𝑏𝑚) 为把数组变成好的所需最少操作次数。

给定数组 𝑎1,…,𝑎𝑛 和 𝑞 次询问。每次询问给出 𝑙,𝑟,求

𝑓(𝑎𝑙,𝑎𝑙+1,…,𝑎𝑟).

2≤𝑛≤194598,1≤𝑞≤1049658,1≤𝑎𝑖≤5032107,1≤𝑙<𝑟≤𝑛。

题解

先把每个 𝑎𝑖 的平方因子去掉,记剩下的平方自由部分为 𝑐𝑖,并令 𝜔(𝑥) 为 𝑥 的不同质因子数。两个平方自由数的乘积为完全平方数,当且仅当它们相等;把 𝑐𝑖,𝑐𝑗 变成相同数的最少操作数为

𝑑(𝑐𝑖,𝑐𝑗)=𝜔(𝑐𝑖)+𝜔(𝑐𝑗)−2𝜔(gcd(𝑐𝑖,𝑐𝑗)).

因此询问就是求区间内点对的最小距离。

按右端点 𝑡 扫描。定义

ℎ𝑡(𝑥,𝑑)=max{𝑗≤𝑡:𝑥|𝑐𝑗,𝜔(𝑐𝑗𝑥)=𝑑},𝑔𝑡(𝑐)=max{𝑗:区间[𝑗,𝑡]的答案≤𝑐}.

空集取 −∞。

加入 𝑐𝑡 时,对每个 𝑥|𝑐𝑡 和每个 𝑑,用 ℎ𝑡−1(𝑥,𝑑) 更新

𝑔𝑡(𝑑+𝜔(𝑐𝑡𝑥));

然后令 ℎ𝑡(𝑥,𝜔(𝑐𝑡𝑥))=𝑡。这里 𝑥 遍历 𝑐𝑡 的约数,也就是点对的可能公共约数;当 𝑥 取到点对的 gcd 时,𝑑+𝜔(𝑐𝑡𝑥) 就是真实距离。

对询问 [𝑙,𝑡],答案为

min{𝑐:𝑔𝑡(𝑐)≥𝑙}.

由对 𝑡 的归纳,𝑔𝑡(𝑐) 恰好是满足区间答案不超过 𝑐 的最大左端点,因此查询公式正确。更新 𝑔 必须先于 ℎ,保证点对的两个下标不同。

复杂度

每个 𝑐𝑡 至多有 7 个不同质因子:前 8 个质数的乘积已经大于 5032107。因此至多有 27=128 个约数,答案只可能在 0,…,14。

加入一个数时枚举约数和 𝑑,查询时枚举 𝑐=0,…,14。时间

𝑂(𝑛⋅27⋅7+14𝑞),

状态按值域开表时空间为 𝑂(𝑉⋅8),其中 𝑉=5032107;若只存出现过的约数,则为 𝑂(𝑛⋅27)。

参考

源码位置