(1)問題概要
ある自然数の階乗(n!)が、〇で何回割り切れるか、あるいは、末尾に0が連続して何個並ぶかを答える問題。
(2)ポイント
ある自然数の階乗(n!)が〇で何回割り切れるか(素因数分解をしたときに〇が何個含まれているか)を調べるときは、
①1~nまでの〇の倍数の個数
②〇²の倍数の個数
③〇³の倍数の個数
④〇⁴の倍数の個数
……
を調べて、
①+②+③+④+……
としたものが答えとなります。
例えば、
30!は3で何回割り切れるか(素因数に3を何個持つか)を考えてみると、
①1~30までに、3の倍数は10個ある(30÷3=10)
②3²の倍数は、3個ある(30÷9=3余り3)
③3³の倍数は、1個ある(30÷27=1余り3)
となるので、答えは、
10+3+1=14回となります。
よくある疑問点としては、
3²は3を2つ持っているのだから、3×2=6としなくてよいのか?
という質問があります。
×2をしなくてよい理由は、3の倍数の中に9の倍数も含まれているからです。
つまり、3の倍数の10個の中に9の倍数の3個も含まれているので、3の倍数の10個をカウントしたときに、9の倍数も1回カウントされているのです。
また、このタイプの問題でよくあるパターンは、「末尾に0が連続して何個並ぶか」というものです。
これは、素因数5の個数を数えればよいことになります。
理由は、
末尾に0が連続して並ぶ個数=10をかけている個数=5×2をかけている個数=5の個数(5の個数が2の個数よりも少ないとき)
だからです。
(3)必要な知識
(4)理解すべきコア