問題一覧 > 通常問題

No.2570 Maximum Greatest Common Divisor

レベル : / AI推定難易度 : 1450 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 41
作問者 : ragna / テスター : deuteridayo 👑 AngrySadEight kusirakusira Magentor 👑 loop0919
お気に入りにしたユーザー ProblemId : 10352 / 自分の提出
問題文最終更新日: 2023-12-01 12:57:54
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
緑以下コンテスト Extra (順位表) の他の問題:

Problem Statement

You are given a sequence $A$ of positive integers of length $N$. You may perform the following operations on this sequence at most $K$ times.

  • Choose one $i$ such that $1 \leq i \leq N$, and increase the value of $A_i$ by $1$.
  • Choose one $i$ such that $1 \leq i \leq N$, and decrease the value of $A_i$ by $1$. However, this operation cannot be performed when $A_i=0$.
Find the maximum possible value of $\gcd(A_1,A_2, \ldots ,A_N)$ after the operations.

Constraints

  • $2 \leq N \leq 100$
  • $1 \leq K < N$
  • $1 \leq A_i \leq 10^{11}$
  • All inputs are integers

Input

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

Output

Output the answer.

Sample

Sample 1
Input
8 5
27 59 46 15 75 87 12 48
Output
3

  • Perform the operation on $A_2$ $1$ time to make it $60$
  • Perform the operation on $A_3$ $1$ time to make it $45$
These $2$ operations make $\gcd(A_1,A_2, \ldots ,A_8)=3$, and this is the maximum.

Sample 2
Input
15 14
959 877 328 628 251 497 495 283 595 897 364 149 2 990 316
Output
4

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