AtCoder Regular Contest 126
翻译中…
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.
翻译中…
样例
Input #1
3 6
3 4 9
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$.
Input #2
3 4
30 10 20
Output #2
10
Doing no operation achieves $\gcd(A_1, A_2, A_3) = 10$.
Input #3
5 12345
1 2 3 4 5
Output #3
2472
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。