No.136 Yet Another GCD Problem

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 289
作問者 :

anta

6 ProblemId : 254 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2015-11-14 17:47:29

正整数の配列 $A$ に対して、 $A$ の総和がちょうど $x$ であるとき、 $A$ を $x$ の分割であると呼ぶ。

整数の配列 $A$ に対して、 $gcd (A) = gcd (A_{1}, A_{2}, \dots, A_{| A |})$ と定義する。

整数 $N, K$ が与えられる。 $2 \leq | A | \leq K$ となる $N$ の分割 $A$ に対し、 $gcd (A)$ を最大化せよ。

N K

1行に空白区切りで整数 $N, K$ ( $2 \leq N \leq 10^{5}$ , $2 \leq K \leq 10^{5}$ )が与えられる。

1行に、問題文の条件を満たす $A$ のうち、 $gcd (A)$ が最大となる $A$ の $gcd (A)$ を出力せよ。

21 2

例えば $A = [7, 14]$ とすると、 $A$ は $21$ の分割になっていて、 $A$ の要素の最大公約数は $\gcd (7, 14) = 7$ となる。

23 100000

23をどのように2つ以上の長さの配列に分割してもその要素の最大公約数は1となる。

100 2

$A = [50, 50]$ が要素の最大公約数が50となる唯一の分割である。

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