题解 P6817 【[PA2013]Filary】

· · 题解

取 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 为值域。

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

参考实现