自动搬运

查看原文

来自洛谷，原作者为

	RiverHamster hope invaluable | 曾经是个OIer

搬运于2025-08-24 22:24:16，当前版本为作者最后更新于2020-09-19 23:28:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

取 $m = 2$，可以得到答案的一个下界是 $\lceil {n \over 2} \rceil$。

直接做很难处理，考虑随机一个值必选。根据答案下界，随机一次能得到最优解的概率大于 $1 \over 2$，因此随机 $20$ 次左右即可。

同余条件即 $m \mid x - y$，$x$ 已经通过随机固定，那么枚举每个数 $y$，将 $|x - y|$ 的所有 素因子 用桶维护，取最大出现次数。

但可能存在合数 $m$，使 $k$ 同样可以取到最大，可以考虑将两个对应 $a_i$ 的位置完全相同 的素因子 “合并”。

如果暴力维护，那么单次尝试 $\mathcal O(n \log^2 V)$，因为合法的素因子只有 $\mathcal O(\log V)$ 个，我们可以考虑给每种 $a_i$ 赋随机权值，对每个素因子维护 xor-Hash 即可。

线性筛出每个数最小素因子，总复杂度 $\mathcal O(V + T\cdot n \log V)$，$T$ 为随机次数，$V$ 为值域。

注意考虑一个素因子重复出现的情况。

参考实现