C - Maximize GCD

Contest Duration: 2021-09-19(Sun) 13:00 - 2021-09-19(Sun) 15:00 (local time) (120 minutes) Back to Home

C - Maximize GCD Editorial

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)$ としてありうる最大値を出力してください。

入力例 1Copy

Copy

3 6
3 4 9

出力例 1Copy

Copy

例えば以下のようにして、 $\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$ である。

入力例 2Copy

Copy

3 4
30 10 20

出力例 2Copy

Copy

操作を一度も行わないことで、 $\gcd(A_1, A_2, A_3) = 10$ を実現できます。

入力例 3Copy

Copy

5 12345
1 2 3 4 5

出力例 3Copy

Copy

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 1Copy

Copy

3 6
3 4 9

Sample Output 1Copy

Copy

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 2Copy

Copy

3 4
30 10 20

Sample Output 2Copy

Copy

Doing no operation achieves $\gcd(A_1, A_2, A_3) = 10$ .

Sample Input 3Copy

Copy

5 12345
1 2 3 4 5

Sample Output 3Copy

Copy