分数: 600 点
问题陈述
给定的是一系列 N 正整数: A = (A_1, A_2, \ldots, A_N)。您可以对此序列执行以下操作,至少为零,最多 K 次:
- 选择 i\in \{1,2,\ldots,N\} 并添加 1 to A_i.
找出最大可能值 \gcd(A_1, A_2, \ldots, A_N) 操作后。
约束
- 2\leq N\leq 3\times 10^5
- 1\leq K\leq 10^{18}
- 1 \leq A_i\leq 3\times 10^5
输入
输入由标准输入按以下格式给出:
N K A_1 A_2 \ldots A_N
输出
打印最大可能值 \gcd(A_1, A_2, \ldots, A_N) 操作后。
示例输入 1
3 6 3 4 9
示例输出 1
5
实现的一种方法 \gcd(A_1, A_2, A_3) = 5 如下。
- 进行操作 i = 1 两次, i = 2 一次,并且与 i = 3 一次,共四次,不超过 K=6.
- 现在我们有 A_1 = 5, A_2 = 5, A_3 = 10,其中 \gcd(A_1, A_2, A_3) = 5.
示例输入 2
3 4 30 10 20
示例输出 2
10
不执行任何操作即可实现 \gcd(A_1, A_2, A_3) = 10.
示例输入 3
5 12345 1 2 3 4 5
示例输出 3
2472