No.136 Yet Another GCD Problem
anta問題文最終更新日: 2015-11-14 17:47:29
問題文
正整数の配列$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となる唯一の分割である。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。