/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
長さ N の整数列 A_1, A_2, \cdots, A_N があります。
次の操作を 0 回以上 K 回以下行うことができます。
- i \neq j なる 1 以上 N 以下の 2 つの整数 i, j を選び、A_i に 1 を足し、A_j に -1 を足す。この操作の後いずれかの要素が負になってもよい。
操作後の 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
例えば、以下のように操作を 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 の全ての要素を割り切るようにはできません。
入力例 3
4 5 10 1 2 22
出力例 3
7
入力例 4
8 7 1 7 5 6 8 2 6 5
出力例 4
5
Score : 500 points
Problem Statement
We have a sequence of N integers: A_1, A_2, \cdots, A_N.
You can perform the following operation between 0 and K times (inclusive):
- Choose two integers i and j such that i \neq j, each between 1 and N (inclusive). Add 1 to A_i and -1 to A_j, possibly producing a negative element.
Compute the maximum possible positive integer that divides every element of A after the operations. Here a positive integer x divides an integer y if and only if there exists an integer z such that y = xz.
Constraints
- 2 \leq N \leq 500
- 1 \leq A_i \leq 10^6
- 0 \leq K \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K
A_1 A_2 \cdots A_{N-1} A_{N}
Output
Print the maximum possible positive integer that divides every element of A after the operations.
Sample Input 1
2 3 8 20
Sample Output 1
7
7 will divide every element of A if, for example, we perform the following operation:
- Choose i = 2, j = 1. A becomes (7, 21).
We cannot reach the situation where 8 or greater integer divides every element of A.
Sample Input 2
2 10 3 5
Sample Output 2
8
Consider performing the following five operations:
- Choose i = 2, j = 1. A becomes (2, 6).
- Choose i = 2, j = 1. A becomes (1, 7).
- Choose i = 2, j = 1. A becomes (0, 8).
- Choose i = 2, j = 1. A becomes (-1, 9).
- Choose i = 1, j = 2. A becomes (0, 8).
Then, 0 = 8 \times 0 and 8 = 8 \times 1, so 8 divides every element of A. We cannot reach the situation where 9 or greater integer divides every element of A.
Sample Input 3
4 5 10 1 2 22
Sample Output 3
7
Sample Input 4
8 7 1 7 5 6 8 2 6 5
Sample Output 4
5