题解：P15019 [UOI 2020 II Stage] 倍乘

· · 题解

题意简述

给定长度为 n 的序列 a，所有元素的质因子均 \le 29。每次操作可以将一个数乘上它的任意一个除数（就是因数）。求有多少个子区间 [l,r] 可以通过不超过 k 次操作使区间内所有数相等。

思路

首先观察这个题目，不难发现 30 以内质因子只有 10 个：2\text,3\text,5\text,7\text,11\text,13\text,17\text,19\text,23\text,29。

接下来上干货！

如果一个区间符合题意，那么所有数的质因子集合相同（否则无法产生或消除质因子）。对每一个质因子，若区间内指数最大为 M，最小为 m，则 M \le m \cdot 2^k（k 步内 m 最多翻 k 倍）。当 k \ge 20 时 2^k 已远超最大指数 20，满足题意。

我们可以使用双指针法，按质因子集合将序列分成极长连续的区间，在每个区间内使用双指针。对每个左端点 L，维护最大右端点 R 使窗口 [L,R] 满足条件，答案累加 R-L+1。

:::success[正确性证明]{open} 固定段内出现的质因子集合 S，设 C = 2^k。对任意区间 I = [l,r]，定义其合法当且仅当

\forall p \in S\text, M_p(I) \le C \cdot m_p(I),

其中 M_p(I) 和 m_p(I) 分别表示 I 中质因子 p 的指数最大值与最小值。下面证明两个单调性质：

右端单调性

若区间 [l,r] 合法，则对任意 l \le r' < r，[l,r'] 也合法。\ 入话：缩小右端点后，最大值 M_p 可能下降，最小值 m_p 可能上升，不等式左边不增、右边不减，故条件保持成立。

因此，对于固定的左端点 l，合法的右端点 r 构成一个前缀，存在最大合法右端点 R(l)，且所有以 l 起头的优美数对恰好是 r = l\text, l+1\text, \dots\text, R(l)，共 R(l)-l+1 个。

左端单调性

若 [l,r] 合法，则对任意 l < l' \le r，[l',r] 也合法。\ 入话：左端点右移，同样缩小了区间，最大值不增、最小值不减，条件更易满足。

由该性质可知，当左端点 L 增加时，上一轮求出的 R 对于新区间 [L+1,R] 依然可行，因此 R 不会减小。这保证了每个元素最多被插入和删除各一次，算法实现正确且线性。 :::

提示：每个质因子开一个大小为 21 的计数数组，记录当前指数值的出现次数，同时维护极值。由于值域很小，插入和删除时暴力更新即可。

本题解“正确性证明”部分完成后使用了 DeepSeek 进行润色。