Pythonで階乗の末尾にn個の0を持つ最小の数mを見つけるプログラム

問題概要

ある数 n が与えられたとき、「m の階乗（m!）の末尾に少なくとも n 個の 0 が並ぶ」ような最小の数 m を求めることを考えます。

例えば、入力が n = 2 の場合、答えは 10 になります。10! = 3628800 と末尾に 0 が 2 個付きますが、9! = 362880 では 0 は 1 個しかないため、0 が 2 個以上現れる最小の数は 10 となるからです。

解法のポイント：5 の因数の個数を数える

階乗の末尾に付く 0 は「10 = 2 × 5」がいくつ作られるかで決まります。階乗の中には 2 の倍数が 5 の倍数よりも圧倒的に多く含まれるため、約数に含まれる 5 の総数を数えれば、それがそのまま末尾の 0 の個数になります。

そこで、まず「1 から n までの各数が持つ 5 の因数の総数」を返す関数 count_fives() を定義します。手順は以下の通りです。

• cnt := 0 で初期化する
• n > 0 の間、次を繰り返す：
  • n := ⌊n / 5⌋（5 で割った商の切り捨て値）
  • cnt := cnt + n
• cnt を返す

この計算方法なら、25 や 125 のように 5 を複数個持つ数も正しくカウントできます。

二分探索で最小の m を求める

count_fives(m) の結果は m に対して単調増加するため、二分探索を使うことで条件を満たす最小の m を効率よく絞り込めます。メイン処理の手順は次の通りです。

• left := 1、right := 5^24 とする（十分に大きな上限値）
• right − left > 5 の間、次を繰り返す：
  • mid := ⌊(right + left) / 10⌋ × 5（5 の倍数に丸めた中央値）
  • fives := count_fives(mid)
  • fives == n の場合：right := mid、left := right − 5 としてループを抜ける
  • fives < n の場合：left := mid
  • それ以外の場合：right := mid
• right を返す

実装例

それでは、実際の Python コードを見てみましょう。

def count_fives(n):
   cnt = 0
   while n > 0:
      n = n // 5
      cnt += n
   return cnt

def solve(n):
   left = 1
   right = 5**24
   while right - left > 5:
      mid = int((right + left) / 10) * 5
      fives = count_fives(mid)
      if fives == n:
         right = mid
         left = right - 5
         break
      elif fives < n:
         left = mid
      else:
         right = mid
   return right

n = 2
print(solve(n))

入力

2

出力

10

まとめ

階乗の末尾の 0 の個数は「5 の因数の個数」と一致するため、まず 5 の個数を数える関数を用意し、その結果をもとに二分探索を行うことで、条件を満たす最小の m を高速に求められます。計算量は O(log m) 程度に抑えられ、非常に大きな n に対しても実用的に動作します。