No.811 約数の個数の最大化
タグ : / 解いたユーザー数 196
作問者 :
Shuz*
/ テスター :
tatyam
問題文
合成数 $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
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。