No.136 Yet Another GCD Problem

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 149
作問者 : antaanta

4 ProblemId : 254 / 出題時の順位表

問題文

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

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

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

入力

N K

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

出力

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

サンプル

サンプル1
入力
21 2
出力
7

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

サンプル2
入力
23 100000
出力
1

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

サンプル3
入力
100 2
出力
50

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

提出ページヘ