C++で解く階乗の末尾ゼロ関数のプリイメージサイズ

問題の概要

階乗の末尾に連続して並ぶ 0 の個数を返す関数 f(x) を考えてみましょう。たとえば 3! = 6 には末尾の 0 がないため f(3) = 0 となり、11! = 39916800 には末尾に 0 が 2 個あるため f(11) = 2 となります。

本記事のテーマは、整数 K が与えられたときに「f(x) = K を満たす非負整数 x が何個存在するか」を求めることです。

たとえば入力が K = 2 の場合、答えは 5 になります。

解法のポイント

n! の末尾に付く 0 の個数は、その階乗に含まれる素因数 5 の個数と一致します。これは 2 の因数のほうが常に十分に多く存在するためです。そこで補助関数 ok(x) では、ルジャンドルの公式に基づき、x を 5, 25, 125, … で順に割った商の総和として 5 の個数を数えます。

さらに、f(x) は x に対して単調非減少であるため、f(x) = K となる最小の x を二分探索で効率的に特定できます。

アルゴリズムの手順

• 補助関数 ok() を定義する。引数は x。
• ret := 0 で初期化する。
• i := 5 から始め、i <= x の間、i := i * 5 として更新しながら次を繰り返す。
  • ret := ret + x / i
• ret を返す。
• メイン処理では以下を実行する。
• K が 0 と等しい場合：
  • 5 を返す。
• low := 1、high := K * 5 とする。
• low < high の間、次を繰り返す。
  • mid := low + (high − low) / 2
  • x := ok(mid)
  • x < K ならば low := mid + 1、それ以外は high := mid
• 最後に、ok(low) が K と等しければ 5 を、そうでなければ 0 を返す。

答えが必ず 0 か 5 になる理由

連続する 5 つの整数の中には 5 の倍数がちょうど 1 つ含まれます。5 の倍数でない整数では末尾ゼロの個数は変化しないため、f(x) = K を満たす x が存在すれば、それは必ず 5 つ連続した整数の区間となります。一方、125! のように 5 の累乗を跨ぐ地点ではゼロの個数が一気に 2 以上増加するため、一部の K は決して実現されません。このため、答えは常に 0 または 5 のいずれかになります。

C++による実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
    lli ok(lli x){
        int ret = 0;
        for(lli i = 5; i <= x; i *= 5){
            ret += x / i;
        }
        return ret;
    }
    int preimageSizeFZF(int K) {
        if(K == 0) return 5;
        lli low = 1;
        lli high = (lli)K * 5;
        while(low < high){
            lli mid = low + (high - low) / 2;
            lli x = ok(mid);
            if(x < K){
                low = mid + 1;
            }else high = mid;
        }
        return ok(low) == K ? 5 : 0;
    }
};
main(){
    Solution ob;
    cout << (ob.preimageSizeFZF(2));
}

入力

2

出力

5