https://beta.atcoder.jp/contests/abc114/tasks/abc114_d
整数$N$が与えられる。$N!$の約数のうち、約数が75個あるものの数を求めよ。
素数$p,q,r$が存在して、整数$p^aq^br^c$の約数の数は$(a+1)(b+1)(c+1)$であることを利用する。
はじめに2から$N$までの整数をすべて素因数分解して結果を足し合わせることで$N!$を素因数分解する。 DPテーブルを $$DP[i][j]=i{\rm 整数iまでをつかったときに約数が}j{\rm 個になるような}N!{\rm の約数の数}$$ として、素数でない$i$については0個含んでいるとして扱えばよくて、$DP[N][75]$が答えになる。遷移は簡単。
Cに時間を使いすぎたね(それでも解けなさい)。