/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
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) としてありうる最大値を求めてください。
制約
- 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 に対して 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
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
Score : 600 points
Problem Statement
Given is a sequence of N positive integers: A = (A_1, A_2, \ldots, A_N). You can do the following operation on this sequence at least zero and at most K times:
- choose i\in \{1,2,\ldots,N\} and add 1 to A_i.
Find the maximum possible value of \gcd(A_1, A_2, \ldots, A_N) after your operations.
Constraints
- 2\leq N\leq 3\times 10^5
- 1\leq K\leq 10^{18}
- 1 \leq A_i\leq 3\times 10^5
Input
Input is given from Standard Input in the following format:
N K A_1 A_2 \ldots A_N
Output
Print the maximum possible value of \gcd(A_1, A_2, \ldots, A_N) after your operations.
Sample Input 1
3 6 3 4 9
Sample Output 1
5
One way to achieve \gcd(A_1, A_2, A_3) = 5 is as follows.
- Do the operation with i = 1 twice, with i = 2 once, and with i = 3 once, for a total of four times, which is not more than K=6.
- Now we have A_1 = 5, A_2 = 5, A_3 = 10, for which \gcd(A_1, A_2, A_3) = 5.
Sample Input 2
3 4 30 10 20
Sample Output 2
10
Doing no operation achieves \gcd(A_1, A_2, A_3) = 10.
Sample Input 3
5 12345 1 2 3 4 5
Sample Output 3
2472