题解

思路

操作后只有一种数，等价于所有 $A_i$ 模 $M$ 同余，也就是 $M$ 整除每个差 $A_i-A_1$。

做法

令 $g=\gcd(|A_2-A_1|,\ldots,|A_N-A_1|)$，存在 $M\ge2$ 当且仅当 $g e1$；全相等时 $g=0$，同样可以选择任意足够大的 $M$ 得到一种数。

若 $g=1$，一种数不可能，而选择 $M=2$ 后余数至多为 0、1 两种，所以答案为 2。

复杂度

线性求 gcd 即可，时间复杂度为 $O(N\log\max A_i)$，额外空间为 $O(1)$。