C++で(1^1)×(2^2)×(3^3)×(4^4)×…×num^numの積に含まれる末尾のゼロの個数を数える方法

整数 num を入力として与えます。この記事の目標は、積 1¹ × 2² × 3³ × … × num^num の計算結果に含まれる「末尾のゼロ（連続する0）」の個数を求めることです。

具体例

入力

num=5

出力

(1^1)*(2^2)*(3^3)*(4^4)*.. の積における末尾のゼロの個数：5

解説

積に含まれる2と5の個数は次のように数えられます。
1^1 * 2^2 * 3^3 * 4^4 * 5^5 = 1^1 * 2^2 * 3^3 * (2^2)^4 * 5^5
したがって、2は合計10個、5は合計5個となります。このうち小さい方は5なので、末尾のゼロの個数は5になります。

入力

num=10

出力

(1^1)*(2^2)*(3^3)*(4^4)*.. の積における末尾のゼロの個数：15

解説

積に含まれる2と5の個数は次のように数えられます。
1^1 * 2^2 * 3^3 * 4^4 * 5^5 * 6^6 * 7^7 * 8^8 * 9^9 * 10^10
= 1^1 * 2^2 * 3^3 * 4^4 * 5^5 * 6^6 * 7^7 * 8^8 * 9^9 * (2*5)^10
したがって、2は合計20個、5は合計15個となります。このうち小さい方は15なので、末尾のゼロの個数は15になります。

アルゴリズムの考え方

ここで紹介するアプローチでは、積に含まれる各数値を素因数分解し、そこに現れる2の個数と5の個数をそれぞれ数えます。各項は自分自身の冪乗（iⁱ）の形になっているため、因数分解全体における2の個数と5の個数のうち小さい方が、そのまま末尾のゼロの個数になります。これは、2×5のペアが1つできるごとに積の末尾に0が1つ追加されるためです。

手順

• 整数 num を入力として受け取ります。

• 関数 count_trailing(int num) は num を引数に取り、(1^1)*(2^2)*(3^3)*(4^4)*…… の積における末尾のゼロの個数を返します。

• カウント用変数 count を 0 で初期化します。

• 2と5の個数を格納するための変数 temp_2 = 0、temp_5 = 0 を用意します。

• for ループを使い、i = 1 から i <= num まで順番に処理します。

• 一時変数 temp に i を代入します。

• temp が2で割り切れる間、temp を半分にしながら、そのたびに temp_2 に i を加算して2の個数を数えます。

• temp が5で割り切れる間、temp を5で割りながら、そのたびに temp_5 に i を加算して5の個数を数えます。

• count = min(temp_2, temp_5) により、2つのカウントの小さい方を求めます。

• count を結果として返します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
int count_trailing(int num){
    int count = 0;
    int temp_2 = 0;
    int temp_5 = 0;
    for (int i = 1; i <= num; i++){
        int temp = i;
        while(temp % 2 == 0 && temp > 0){
            temp = temp / 2;
            temp_2 = temp_2 + i;
        }
        while (temp % 5 == 0 && temp > 0){
            temp = temp / 5;
            temp_5 = temp_5 + i;
        }
    }
    count = min(temp_2, temp_5);
    return count;
}
int main(){
    int num = 5;
    cout<<"Count of number of trailing zeros in (1^1)*(2^2)*(3^3)*(4^4)*.. are: "<<count_trailing(num);
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

Count of number of trailing zeros in (1^1)*(2^2)*(3^3)*(4^4)*.. are: 5