← 返回题目列表

AtCoder · abc136_e

E. 最大 GCD

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

分数: 500 点

问题陈述

我们有一系列 N 整数: A_1, A_2, \cdots, A_N.

您可以在以下时间之间执行以下操作: 0 和 K 次(含):

  • 选择两个整数 i 和 j 这样 i \neq j,每个之间 1 和 N (含)。添加 1 to A_i 和 -1 to A_j,可能产生负元素。

计算除以每个元素的最大可能正整数 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 操作后。


示例输入 1

2 3
8 20

示例输出 1

7

7 将除以每个元素 A 例如,如果我们执行以下操作:

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

我们无法达到以下情况: 8 或更大的整数除以每个元素 A.


示例输入 2

2 10
3 5

示例输出 2

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.


示例输入 3

4 5
10 1 2 22

示例输出 3

7

示例输入 4

8 7
1 7 5 6 8 2 6 5

示例输出 4

5