题解：P14566 【MX-S12-T1】取模

天崩开局J炸S炸

数组 $a$，正整数 $p$，把每个 $a_i$ 除以 $p$ 的余数放进数组 $b$，你的得分就是 $b$ 中max减min。问最大得分是多少

第一步：看看 p 很大时的情况 如果 $p$ 比数组中最大的数还要大，那么每个数除以 $p$ 的余数就是它自己。 这时候得分就是： $\Large\max(a) - \min(a)$

第二步：看看 p 比较小时的情况 余数只能在 $0$ 到 $p-1$ 之间，所以最大值减最小值最大只能是 $p-1$。 如果 $p$ 很小，这个上界也很小，就舍弃掉

那问题来了： 如何让差值变大？ 我们想要让余数中有一个是 $p-1$（最大），还有一个是 $0$（最小），这样差值就是 $p-1$ 什么时候会出现 $p-1$ 呢？当某个数 $x$ 满足 $x \bmod p = p-1$，也就是 $x+1$ 能被 $p$ 整除 什么时候会出现 $0$ 呢？当某个数 $y$ 能被 $p$ 整除 所以我们要找的 $p$ 要同时是某个 $a_i$ 的约数，也是某个 $a_j+1$ 的约数

直接找所有可能的 $p$ 太麻烦，数据太大时会超时。 我们想想，其实最大得分只有两种可能：

直接取 $p$ 很大，得分是 $\max(a) - \min(a)$

取 $p$ 约为最大值的一半，这样可能得到大约 $\lfloor \frac{\max(a)}{2} \rfloor$ 的得分 那最终就是： $\LARGE \max\left( \max(a) - \min(a),\ \left\lfloor \frac{\max(a)}{2} \right\rfloor \right)$

第二次写文，求通