問題一覧 > 通常問題

No.2570 最大最大公約数

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 50
作問者 : ragnaragna / テスター : 👑 deuteridayodeuteridayo AngrySadEightAngrySadEight kusirakusirakusirakusira MagentorMagentor loop0919loop0919
3 ProblemId : 10352 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-12-01 12:57:54

問題文

長さ $N$ の正整数列 $A$ が与えられます。あなたはこの正整数列に対して次に示す操作を $K$ 回以下行えます。

  • $1 \leq i \leq N$ なる $i$ をひとつ選び、 $A_i$ の値を $1$ 増やす。
  • $1 \leq i \leq N$ なる $i$ をひとつ選び、 $A_i$ の値を $1$ 減らす。ただし、 $A_i=0$ の時はこの操作を行えない。
操作後の $\gcd(A_1,A_2, \ldots ,A_N)$ の値の最大値を求めてください。

制約

  • $2 \leq N \leq 100$
  • $1 \leq K < N$
  • $1 \leq A_i \leq 10^{11}$
  • 入力は全て整数

入力

$N$ $K$
$A_1$ $A_2$ $\ldots$ $A_N$

出力

答えを出力してください。

サンプル

サンプル1
入力
8 5
27 59 46 15 75 87 12 48
出力
3

  • $A_2$ に操作を $1$ 回行って $60$ にする
  • $A_3$ に操作を $1$ 回行って $45$ にする
この $2$ 回の操作で $\gcd(A_1,A_2, \ldots ,A_8)=3$ にでき、これが最大です。

サンプル2
入力
15 14
959 877 328 628 251 497 495 283 595 897 364 149 2 990 316
出力
4

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。