题目描述

塔子哥有一个长度为 n 的数组 a。他想要使得所有$a_i$的最大公因子是一个素数。即:$gcd(a_1,a_2,...,a_n)$是一个素数。他可以对数组进行任意次操作。具体的:每次操作，他会选择$i,j$两个下标，同时执行:$a_i=a_i+2,a_j=a_j-2$

请问他是否有可能在任意次操作内将数组变成符合要求的，如果可以，请输出所有可能的最大公因数。注意，这里要保证$a_j$，在操作后仍然是正数，即不能选择$a_j\le 2$.

题目思路

观察发现，每次操作不会改变每个数字的奇偶性，且数组的总和是不会改变的。

考虑每个元素的奇偶性，当所有元素都是偶数时，最大公因数（gcd）起码是偶数（因为操作不改变奇偶性），有一种方法可以让一个元素降低为2，这样就有一个2作为素数的答案。

当有奇数和偶数时，考虑数组的总和sum的素因子，由于有奇数存在，所以2不能计入答案，对于其它的素因子x，设cnt是偶数的数量，当x * n + cnt <= sum时，一定存在一种方法使得该素因子可以成为最大公因数。

这里判断需要加上cnt的原因是偶数至少应该是2 * x，排除了2，x一定是奇数。