C++で桁の階乗の積が等しくなる最大の数を求める方法

この記事では、与えられた数 N の各桁の階乗の積と等しくなるような、先頭や末尾に 0 や 1 を含まない最大の数を求める方法を解説します。

まず、具体例を使って問題を理解しましょう。

入力 − N = 4912

出力 − 73332222

説明 − 4! × 9! × 1! × 2! = 7! × 3! × 3! × 3! × 2! × 2! × 2! × 2! = 17,418,240

入力 − N = 340

出力 − 3322

なぜ素数の階乗に分解するのか

0! と 1! はどちらも 1 に等しいため、0 と 1 の桁は積に影響を与えません。一方、4!、6!、8!、9! はそれぞれ以下のように、素数の階乗の積で表すことができます。

• 4! = 3! × 2! × 2!
• 6! = 5! × 3!
• 8! = 7! × 2! × 2! × 2!
• 9! = 7! × 3! × 3! × 2!

つまり、答えとなる数は 2、3、5、7 のみで構成されます。桁数が多いほど数は大きくなるため、分解できる桁はすべて素数の階乗の積に置き換えることで、条件を満たす最大の数が得られます。なお、与えられた数が 0 と 1 のみで構成されている場合は、答えを求めることができません。

プログラムで使用するアプローチ

• MaxNum() 関数内で、桁の総数を格納する int 型の変数 total_digits を作成し、さらに各数字の出現回数を格納する int 型の配列 Frq[] = {0} を初期化します。

• i = 0 から i < total_digits までループし、各桁が素数（2、3、5、7）であるかどうかを判定します。

• 現在の桁が素数であれば、配列 Frq[] の該当する位置に 1 を加算します。

• 桁が素数でない場合は、個別の if 文で 4、6、8、9 のいずれかに該当するかを確認し、その桁を素数の階乗の積に分解して、対応する頻度を加算します。

• 最終的な答えを格納するための空の文字列 ans を作成します。

• 最終ステップに進む前に、元の数が 1 と 0 のみで構成されているかどうかを確認します。その場合は元の文字列をそのまま返し、そうでなければ次のステップへ進みます。

• i = 9 から i >= 2 までループします。int 型の変数 C = Frq[i] を初期化し、for ループ内で while (C--) という条件の while ループを作成し、その中で ans += (char)(i + 48) を実行することで、大きい桁から順に答えを文字列 ans に格納していきます。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
string MaxNum(string str){
    int total_digits = str.length();
    int Frq[15] = { 0 };
    //各数字の出現回数を取得
    for (int i = 0; i < total_digits; i++){
        if (str[i] == '1'|| str[i] == '2'|| str[i] == '3'|| str[i] == '5'|| str[i] == '7'){
            Frq[str[i] - 48] += 1;
        }
        // 4! = 2! * 2! * 3!
        if (str[i] == '4'){
            Frq[2] += 2;
            Frq[3]++;
        }
        // 6! = 5! * 3!
        if (str[i] == '6'){
            Frq[5]++;
            Frq[3]++;
        }
        // 8! = 7! * 2! * 2! * 2!
        if (str[i] == '8'){
            Frq[7]++;
            Frq[2] += 3;
        }
        // 9! = 7! * 3! * 3! * 2!
        if (str[i] == '9'){
            Frq[7]++;
            Frq[3] += 2;
            Frq[2]++;
        }
    }
    string ans = "";
    //数が1と0のみで構成されている場合
    if (Frq[1] == total_digits || Frq[0] == total_digits || (Frq[0] + Frq[1]) == total_digits){
        return str;
    }
    else{
        //条件を満たす最大の数を生成
        for (int i = 9; i >= 2; i--){
            int C = Frq[i];
            while (C--){
                ans += (char)(i + 48);
            }
        }
        return ans;
    }
}
//メイン関数
int main(){
    string str = "340";
    cout << MaxNum(str);
    return 0;
}

出力

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

3322