問題一覧 > 通常問題

No.2570 最大最大公約数

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

問題文

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

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

制約

  • 2≤N≤1002 \leq N \leq 100
  • 1≤K<N1 \leq K < N
  • 1≤Ai≤10111 \leq A_i \leq 10^{11}
  • 入力は全て整数

入力

NN KK
A1A_1 A2A_2 …\ldots ANA_N

出力

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

サンプル

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

  • A2A_2 に操作を 11 回行って 6060 にする
  • A3A_3 に操作を 11 回行って 4545 にする
この 22 回の操作で gcd⁡(A1,A2,…,A8)=3\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もしくは右上の雲マークをクリックしてアカウントを作成してください。