E - 最大公因数

得分：500分

问题描述

我们有一个长度为$N$的整数序列：$A_1, A_2, \cdots, A_N$。

你可以执行如下操作$0$至$K$次（包括$0$和$K$两次）：

• 选择两个整数$i$和$j$，$i \neq j$，并且$i$和$j$都在$1$至$N$之间（包括$1$和$N$）。向$A_i$加$1$，向$A_j$减$1$，可能产生负数。

计算在操作之后，能够整除$A$中的每个元素的最大正整数。如果一个正整数$x$能够整除一个整数$y$，则存在一个整数$z$满足$y = xz$。

约束

• $2 \leq N \leq 500$
• $1 \leq A_i \leq 10^6$
• $0 \leq K \leq 10^9$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入中给出：

$N$ $K$

$A_1$ $A_2$ $\cdots$ $A_{N-1}$ $A_{N}$

输出

输出能够整除$A$中的每个元素的最大正整数。

2 3
8 20

7

如果我们执行以下操作：

• 选择$i = 2, j = 1$。$A$变为$(7, 21)$。

则$7$能够整除$A$中的每个元素。不能够找到一个大于等于$8$的整数能够整除$A$中的每个元素。

2 10
3 5

8

考虑执行以下五次操作：

• 选择$i = 2, j = 1$。$A$变为$(2, 6)$。
• 选择$i = 2, j = 1$。$A$变为$(1, 7)$。
• 选择$i = 2, j = 1$。$A$变为$(0, 8)$。
• 选择$i = 2, j = 1$。$A$变为$(-1, 9)$。
• 选择$i = 1, j = 2$。$A$变为$(0, 8)$。

那么，$0 = 8 \times 0$，$8 = 8 \times 1$，所以$8$能够整除$A$中的每个元素。不能够找到一个大于等于$9$的整数能够整除$A$中的每个元素。

4 5
10 1 2 22

7

8 7
1 7 5 6 8 2 6 5

5

由于评测机性能问题，已删除部分测试点。