ABC114-D：756(400)

問題

https://atcoder.jp/contests/abc114/tasks/abc114_d

整数 N が与えられます。N! の約数のうち、約数をちょうど 75 個もつ正の整数は何個あるでしょうか。

制約

  • 1 \le N \le 100

考え方

75 という整数に着目する解法*1と一般的に解く方法がある。一般的に解く方法を考える。

まず約数を i 個持つ数に約数を j 個持つ数をかけると、約数を i \times j 個持つ数となる。

そこで

dp \lbrack i \rbrack \lbrack j \rbrack := i 番目の素因数まで考えたときに約数を j 個もつ数の個数

とする。また N! を素因数分解した素因数をそれぞれ p_i とし、その素因数の個数を cnt_i としておく。すると i 番目の素因数による約数の個数 take 個と、 i-1 番目までの素因数をもとに求められる約数の個数 have 個をかけ合わせて、約数を take \times have 個持つ数を作ることができる。take は 素因数p_i が cnt_i 個存在することから 1 \le take \le cnt_i+1 個を選ぶように素因数を選ぶことができる。そのように考えると以下のようなDP遷移を考えることができる。

dp \lbrack i+1 \rbrack \lbrack have \times take \rbrack += dp \lbrack i \rbrack \lbrack have \rbrack

解は素因数の個数を M として dp \lbrack M \rbrack \lbrack 75 \rbrack となる。

Submission #3834644 - AtCoder Beginner Contest 114

どこに着目して考察するべきだったか

まず約数を i をもつ数と約数を j をもつ数をかけ合わせると約数 i \times j 個もつ数になることがわかる。約数 i \times j 個を小さいサイズから順番に解くことができることがわかる。

何がバグっていたか

得た知見

約数を i 個持つ数に約数を j 個持つ数をかけると、約数を i \times j 個持つ数となる

類題

*1:75 = 3 \times 5 \times 5 であるから約数がちょうど 75 個になる素因数の組み合わせの数を求める解法