Pythonで1からkまでのすべての数で割り切れる最小の整数xの末尾ゼロの個数を求めるプログラム

問題の概要

ある数 k が与えられたとき、1 から k までのすべての整数で割り切れる最小の正整数 x を考えます。つまり、x が 1 から k までのすべての数の倍数となるような最小の値です。この x の末尾に連続して並ぶゼロ（後続ゼロ）の個数を求めるのが課題です。

例えば、入力が k = 6 の場合を考えてみましょう。このとき条件を満たす最小の x は 60 です。60 は 1、2、3、4、5、6 のすべてで割り切ることができます。そして 60 の末尾にはゼロが 1 個あるため、出力は 1 となります。

解決のためのアプローチ

この問題は、次の手順で解くことができます。

• res := 0、x := 1 と初期化します。

• x × 5 ≤ k である間、次の処理を繰り返します。

  • res を 1 増やします。

  • x を 5 倍します。

• 最後に res を返します。

仕組みの解説

1 から k までのすべての数で割り切れる最小の数は、これらの数の最小公倍数（LCM）です。数の末尾にあるゼロの個数は、その数に含まれる約数 2 と 5 のペアの数で決まります。1 から k までの範囲では 2 のべき乗の方が 5 のべき乗よりも多く現れるため、末尾ゼロの個数は 5 のべき乗の指数によって決まります。したがって、「5 の何乗が k 以下になるか」を数えることで答えが求められます。

実装例

以下のコードで実際の動作を確認してみましょう。

サンプルコード

class Solution:
    def solve(self, k):
        res = 0
        x = 1
        while x * 5 <= k:
            res += 1
            x *= 5
        return res

ob = Solution()
k = 6
print(ob.solve(k))

入力

6

出力

1

このように、シンプルなループ処理だけで O(log k) の計算量で効率よく答えを求めることができます。