ABC114 D - 756 - ツバサの備忘録

問題
 提出コード
バグを生やしやすい問題です。相変わらずこういう問題でバグを生やしてしまいます。

解法

$N!$ をまずは素因数分解し、それぞれの素因数が何回登場しているかを調べます。これは、それぞれについて $O( \sqrt{N})$ で調べることができるので、全体で $O(N \sqrt{N} )$ になります。
素因数分解が完了したら、いよいよ約数が75個になるような数を数え上げていきます。
このような数を作成するには、以下のようなパターンが存在します。

1種類の素因数を74個使用した数
2種類の素因数をそれぞれ2個、24個使用した数
2種類の素因数をそれぞれ4個、14個使用した数
3種類の素因数をそれぞれ3個、5個、5個使用した数

ということで、あとはこれらの条件を満たす個数を数え上げることができれば、答えが求まります。
まずは、 $N!$ の素因数を、登場した回数によって5パターンに分けます。
素因数の個数が74回以上、24以上74未満、14以上24未満、4以上14未満、4未満です。
それぞれをパターン0,1,2,3,4と割り振っていきます。

さて、最初に調べた条件に、これらのパターンを当てはめていきます。

1種類の素因数を74個使用した数
ここに使用できる素因数はパターン0の素因数のみです。
パターン0の個数がそのまま答えになります。
2種類の素因数をそれぞれ2個、24個使用した数
前者はすべてのパターン、後者はパターン1もしくは0が使用できます。
前者と後者で使用するパターンが違うときは、それぞれのパターンの個数の積で、同じときは、(使用するパターンの個数)×(使用するパターンの個数-1)で数えることができます。
2個しようするのと、24個使用するのは全く違うものなので、組み合わせではなく順列になります。
2種類の素因数をそれぞれ4個、14個使用した数
数え方は上と同様です。使用できるパターンは、前者がパターン0~3、後者が0~2です。
3種類の素因数をそれぞれ3個、5個、5個使用した数
このパターンのみ注意が必要です。5個使用する素因数が2つあるので、ここだけ順列ではなく組み合わせを調べる必要があります。
3個使用する素因数はすべてのパターン、5個使用する素因数はパターン4以外が使用できます。
使用するパターンをi,j,kとし、それぞれ3個、5個、5個と割り振ることにします。
ここで場合分けをしていきます。被り防止のため、kはj以上としておきます。
1) i=j=kのとき
　　(iの個数)×(iの個数-1)×(iの個数-2)/2で求めることができます。
2)i=jのとき、もしくはi=kのとき
　　(iの個数)×(iの個数-1)×(iとは値が異なる、jもしくはkの個数)となります。
3)それ以外のとき
　　(iの個数)×(jの個数)×(kの個数)となります。

あとは、これらをすべて全探索して、和を求めれば答えとなります。