AT_arc126_c [ARC126C] Maximize GCD

题目描述

给定一个由 $N$ 项组成的正整数序列 $A = (A_1, A_2, \ldots, A_N)$。你可以对该数列进行 $0$ 次以上、$K$ 次以下的如下操作：

• 选择一个 $i \in \{1, 2, \ldots, N\}$，将 $A_i$ 加 $1$。

请你求出经过操作后，$\gcd(A_1, A_2, \ldots, A_N)$ 可能取得的最大值。

输入格式

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

$N$ $K$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出操作后 $\gcd(A_1, A_2, \ldots, A_N)$ 可能取得的最大值。

输入输出样例 #1

输入 #1

3 6
3 4 9

输出 #1

5

输入输出样例 #2

输入 #2

3 4
30 10 20

输出 #2

10

输入输出样例 #3

输入 #3

5 12345
1 2 3 4 5

输出 #3

2472

说明/提示

限制条件

• $2 \leq N \leq 3 \times 10^5$
• $1 \leq K \leq 10^{18}$
• $1 \leq A_i \leq 3 \times 10^5$

样例解释 1

例如，可以如下操作使得 $\gcd(A_1, A_2, A_3) = 5$：

• 对 $i = 1$ 操作 $2$ 次，对 $i = 2$ 操作 $1$ 次，对 $i = 3$ 操作 $1$ 次。总操作次数为 $4$，不超过 $K = 6$。
• 操作后，$A_1 = 5$，$A_2 = 5$，$A_3 = 10$，此时 $\gcd(A_1, A_2, A_3) = 5$。

样例解释 2

如果一次操作也不进行，则 $\gcd(A_1, A_2, A_3) = 10$。

由 ChatGPT 4.1 翻译