← 返回题目列表

AtCoder · arc126_c

C. 最大化 GCD

中文机器翻译题面 查看原题

分数: 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