ARC152C 题解

blog。可能是很简单的，但是我实在是不会这种神秘题 /ll /ll。

• Conclusion1. 记 \(d=a_n-a_1\)，则极差始终等于 \(d\)。证明显然。
• Conclusion2. 操作极值时，最小值始终变化为 \(d\)，并且可以进行无限次这样的变化。证明显然。

题意转变：最小化 \((\texttt{最小值} \bmod d)\)，且最小值始终非负，输出这个值 \(+d\)。

由 Conclusion2，可以通过提前加上充分多个 \(d\) 来避免负数的问题。

题意转变：最小化 \((\texttt{最小值} \bmod d)\)，输出这个值 \(+d\)。

操作 \(x\) 可以使 \(a_1\to 2x-a_1\)，即 \(a_1\) 加上了 \(2(x-a_1)\)，再操作下原本的 \(a_n\) 就可以使最小值加上 \(2(x-a_1)\)。

同理，我们也可以使最小值减去 \(2(x-a_1)\)。于是我们有：

• Conclusion3. 最小值可以任意加减 \(2(a_i-a_1)\) 无限次。

由裴蜀定理，线性组合这些东西，可以使最小值任意加减 \(g=\gcd\{d, 2(a_2-a_1), 2(a_3-a_1), \cdots, 2(a_n-a_1)\}\) 次，答案即 \((a_1\bmod g) + d\)。模拟即可。\(O(n)\)。