JOI 難易度5 factorial

競プロ

問題リンク

まず、 N を素因数分解し N={P_1}^a \times {P_2}^b \times \dots で考えてみます。( P はそれぞれ素数)

この時 N で割り切ることのできる最小の M! とは M \leq max(P_1a,P_2b, \dots) です。
これは (Pa)! が必ず素因数として P を a 個以上もつためであり、 P_1a \leq P_2b ならば、 (P_2b)! は (P_1a)! を内包します。( P_1 と P_2 は互いに異なる素数なので、 max(P_1a,P_2b)! \div N は必ず割り切れます)

M! が 素因数として P を a 個持つとき、最小の M は M \leq Pa です。
P が素数のために、 P の倍数としてしか因数に P が出現しないため P^a で割り切れる M! の最小の M とは、 M = Pa です。

これらから、 N で割り切ることのできる最小の M! の M とは、 max(P_1a, P_2b, \dots) となります。