题解

思路

把每个原数视为若干最终因子的乘积。小范围直接枚举乘法划分；更大范围从大到小枚举允许的因子下界，并动态维护每个数所需的最小上界。

1. 操作的本质

不断把 $x$ 拆成 $p,q$，最终得到的是若干个大于 $1$ 的整数，它们的乘积仍为 $x$。因此，对每个原数，我们是在选择它的一种乘法划分。数 $1$ 无法被操作，只能保留为 $1$。

做法

子任务 1：枚举乘法划分

当 $m\le 30$ 时，可以递归枚举每个数的所有最终乘法划分。对所有原数的划分方案做深度优先搜索，维护已经选出的因子的最小值和最大值，即可得到最小差值。

这是一个直接依据操作定义得到的独立算法。

固定因子下界

设当前允许出现的最小因子为 $L$。令 $f[x]$ 表示把 $x$ 拆成若干个不小于 $L$ 的因子后，最大因子的最小可能值。

从大到小枚举 $L$。起初保留 $x$ 本身，所以 $f[x]=x$。当新允许因子 $L$ 时，若 $x$ 是 $L$ 的倍数并且 $x/L\ge L$，可以先取出一个因子 $L$，再最优拆分 $x/L$：

$$f[x]\leftarrow\min\bigl(f[x],\max(L,f[x/L])\bigr).$$

按照 $x=L^2,L(L+1),\ldots$ 的顺序更新时，$f[x/L]$ 已经包含重复使用因子 $L$ 的情形。

只有 $L\le\min A$ 时，所有原数都能使用当前下界。此时所需的最小上界为

$$R=\max_{a_i\in A}f[a_i],$$

候选答案为 $R-L$。若集合中含有 $1$，还要用 $L=1$ 计算一次；因子 $1$ 不能参与拆分，所以不执行转移。

子任务 2：逐次扫描原数组

对每个 $L$ 完成上述转移后，扫描全部 $a_i$ 求 $R$。复杂度为

$$O(m\log m+nm),$$

足以通过 $n\le200,m\le2000$。

子任务 3：有序映射维护当前最大值

用有序映射记录当前各个上界对应的原数组元素个数。每当 $f[x]$ 变小时，删除旧上界的出现次数并加入新上界；映射末尾就是当前最大值。复杂度多一个对数，适合 $m\le200000$。

子任务 4：频次数组维护当前最大值

用 $cnt[v]$ 记录当前有多少个原数组元素的 $f[a_i]$ 等于 $v$。当某个 $f[x]$ 变小时，按照 $x$ 在原数组中的出现次数，把对应计数从旧值移到新值。再用一个只会递减的指针维护最大的非空位置，就能在 $O(1)$ 均摊时间得到 $R$。

调和级数给出全部转移次数为 $O(m\log m)$。

6. 正确性证明

引理 1 对固定下界 $L$，转移结束后，$f[x]$ 等于所有因子均不小于 $L$ 的乘法划分中最大因子的最小值。

证明：保留 $x$ 对应单因子划分。任何使用新因子 $L$ 的划分都能去掉一个 $L$，剩余部分是 $x/L$ 的合法划分；转移恰好取二者最大值。反之，每次转移都会构造出一个乘积为 $x$ 且所有因子不小于 $L$ 的合法划分。按 $x$ 递增更新还覆盖了多个 $L$。归纳可得结论。

引理 2 对固定 $L$，使全部最终因子不小于 $L$ 时，可能达到的最小全局最大值为 $\max_i f[a_i]$。

证明：每个原数都必须至少达到其最优上界 $f[a_i]$，所以上式是下界；分别采用达到 $f[a_i]$ 的划分即可同时达到该上界。

定理 算法输出最小可能平衡值。

证明：任一最终集合都有实际最小值 $L$，算法枚举到该 $L$ 时，由引理 1、2 得到不劣于该方案的候选值。另一方面，每个候选值都由合法划分构造，所以不会小于真实最优值。两边结合即得结论。

复杂度

子任务 1 的复杂度为所有乘法划分组合数乘以每次合并的常数代价。子任务 2 的时间复杂度为 $O(m\log m+nm)$。子任务 3 的时间复杂度为 $O(m\log^2m+n)$。满分算法的时间复杂度为 $O(n+m\log m)$。后三者的空间复杂度均为 $O(m+n)$。