ABC #114 D
ある数の約数の数は, その数を素因数分解すると \(p_1^{q_1} p_2^{q_2} \cdots\) となるとき, \((q_1+1)(q_2+1) \cdots\) で表せる. 約数の数が \(75\) になるためには, \(75 = 3 \cdot 5^2\) であるので, 以下の場合になる.
- \[q_1 = 2, q_2 = 4, q_3 = 4\]
- \[q_1 = 2, q_2 = 24\]
- \[q_1 = 4, q_2 = 14\]
- \[q_1 = 74\]
\(N!\) を素因数分解してそのべき乗数を記録しておく. このうち \(q_i \geq 2\) の素因数しか使わないのでそれ以外は捨てていい. あとは素因数を1-3個拾ってそれが上のパターンに当てはまるかどうかを全探索で数え上げる. \(51\) 以上の素数は出現回数が1回以下になり, \(50\) 以下の素数は15個しかないので, 十分に間に合う.