Official

C - Pivot Editorial by evima


The given operation is equivalent to moving each term to the symmetrical position with respect to the chosen value \(s\) on the number line. Therefore, the difference between the minimum and maximum values is constant, so let us minimize the minimum value instead. Let \(d\) be the difference between the minimum and maximum.

When the operation is performed by choosing the minimum or maximum value as \(s\), the minimum value increases or decreases by \(d\). Therefore, if the remainder when the minimum value is divided by \(d\) is \(r\), one can use this action to make the final minimum value \(r\).

Next, let us try to make \(r\) as close to \(0\) as possible. \(r\) changes when one chooses some term that is not the minimum or maximum value as \(s\). More specifically, it changes by \(2(s-m)\), where \(m\) is the minimum value. This action cannot be done twice in a row since doing it once reverses the relative positions of the terms. However, after performing a reversal with respect to the maximum value, which does not change \(r\), one can again change \(r\) by \(2(s-m)\). Thus, this action can be done any number of times, so \(r\) can be changed by any \(t\) such that there is \(k\) \((\geq 0)\) such that \(2(s-m)k\equiv t\) \((\mathrm{mod}\) \(d)\). Additionally, such positive \(k\) exists for \(t\) that is a multiple of \(\mathrm{gcd}(d,2(s-m))\) (\(\mathrm{gcd}\) denotes the greatest common divisor of some numbers). Thus, \(r\) can be changed by any multiple of \(\mathrm{gcd}(d,2(s-m))\).

One can use any term for this action, so \(r\) can be changed by any multiple of \(\mathrm{gcd}(d,2(a_1-m),2(a_2-m),...,2(a_N-m)) = g\) as a whole. Therefore, the answer is \(m\) \(\mathrm{mod}\) \(g+d\).

posted:
last update: