AT_abc136_e [ABC136E] Max GCD

题目描述

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

你可以进行如下操作 $0$ 次或多次，最多不超过 $K$ 次：

• 选择 $1$ 到 $N$ 之间的两个整数 $i,\ j$，且 $i \neq j$，将 $A_i$ 加 $1$，将 $A_j$ 减 $1$。操作后，序列中的某些元素可以变为负数。

请计算，经过操作后，作为能整除 $A$ 的所有元素的正整数中的最大值是多少。这里，正整数 $x$ 能整除整数 $y$，是指存在某个整数 $z$，使得 $y = xz$。

输入格式

输入以如下格式从标准输入读入：

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

输出格式

输出经过操作后，能整除 $A$ 的所有元素的正整数中的最大值。

样例 1

输入

2 3
8 20

输出

7

样例 2

输入

2 10
3 5

输出

8

样例 3

输入

4 5
10 1 2 22

输出

7

样例 4

输入

8 7
1 7 5 6 8 2 6 5

输出

5

说明/提示

限制条件

• $2 \leq N \leq 500$
• $1 \leq A_i \leq 10^6$
• $0 \leq K \leq 10^9$
• 所有输入均为整数

样例解释 1

例如，可以通过如下操作使 $7$ 能整除 $A$ 的所有元素：

• 令 $i = 2, j = 1$，此时 $A$ 变为 $(7, 21)$。 此外，无法使 $8$ 或更大的整数整除 $A$ 的所有元素。

样例解释 2

例如，可以进行如下 $5$ 次操作：

• 令 $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$ 的所有元素。

由 ChatGPT 4.1 翻译