No.811 約数の個数の最大化

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 99
作問者 : Shuz*Shuz* / テスター : tatyamtatyam
7 ProblemId : 2337 / 出題時の順位表

問題文

合成数 $N$ より小さく、 $N$ と共通の素因数を $K$ 個以上持つような自然数の中で、最も約数の多い自然数 $M$ を出力するプログラムを作成せよ。$M$ が複数存在する場合は、最小の $M$ を出力せよ。

ただしここでいう素因数の個数は、同じ素因数でも複数ある場合には別々に数えるものとする。
例: $4$ と $8$ の共通の素因数は $\{2, 2\}$ で、その個数は $2$ である。

補足 ある数以下の自然数の中で約数の個数が最も多い自然数を高度合成数という。本問は $N$ 以下の高度合成数を尋ねている訳ではないので注意が必要である。

入力

$N\ K$

1行目に合成数 $N$ と自然数 $K$ が空白区切りで与えられます。

出力

$N$ より小さく、 $N$ の素因数のうち $K$ 個以上の素因数を持つ、約数の個数が最大の自然数の中で最小の $M$ を出力してください。

制約

$4 \le N \le 100000$
$1 \le K \le 15$
$K <$ ($N$ の素因数の個数)

サンプル

サンプル1
入力
48 4
出力
24

$48=2\times2\times2\times2\times3$ であり、 $M$ はこのうち $4$ つの素因数を持つから、 $M$ は $2\times2\times2\times2=16$ または $2\times2\times2\times3=24$ を約数に持つ。このような自然数の中で、 $N$ より小さく、約数の個数が最大なものは $M=24$ のときその約数は $1,2,3,4,6,8,12,24$ の $8$ 個で、これが最大であるから、24を出力する。

サンプル2
入力
1000 1
出力
840

サンプル3
入力
90720 9
出力
75600

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。