C++で解く最小因数分解：各桁の積が元の数と一致する最小の整数を求める

問題概要

正の整数 x が与えられたとき、各桁の数字を掛け合わせると x と等しくなるような、最も小さい正の整数 b を求めます。そのような答えが存在しない場合は 0 を返します。

例えば、入力が 48 の場合、出力は 68 となります。これは 6 × 8 = 48 を満たす整数の中で最も小さいものだからです。

解法のアプローチ

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

• ret := 0、mul := 1 として初期化する
• a < 2 の場合は、a をそのまま返す
• i を 9 から 2 まで 1 ずつ減らしながらループする
  • a mod i が 0 である間、以下を繰り返す
    • ret := i * mul + ret
    • mul := mul * 10
    • a := a / i
• (a < 2 かつ ret が無限大より小さければ ret を、そうでなければ 0 を返す)

なぜ 9 から順に割っていくのか

ポイントは大きい約数から先に取り出すことです。先に取り出した桁ほど下位の桁（一の位、十の位…）に配置されるため、大きな数字をできるだけ下の桁に置くことで、結果として得られる数が最小になります。また、4・6・8・9 のような合成数を優先的に使うことで、桁数そのものを抑える効果もあります。例えば 36 なら 9 × 4 = 36 なので「49」となり、「66」（6 × 6）よりも小さくなります。

さらに、2〜9 のどれでも割り切れず余りが 1 より大きく残った場合は、単一の桁で表現できないことを意味するため、答えは存在せず 0 を返します。

実装例

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

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   int smallestFactorization(int a) {
      lli ret = 0;
      lli mul = 1;
      if (a < 2)
         return a;
      for (lli i = 9; i >= 2; i--) {
         while (a % i == 0) {
            ret = i * mul + ret;
            mul *= 10;
            a /= i;
         }
      }
      return a < 2 && ret < INT_MAX ? ret : 0;
   }
};
main(){
   Solution ob;
   cout << (ob.smallestFactorization(48));
}

入力

48

出力

68

計算量と注意点

このアルゴリズムは、各除数 i（2〜9）に対して a を繰り返し割っていくだけなので、時間計算量は O(log a) 程度と非常に効率的です。また、途中計算には long long 型を使用してオーバーフローを防ぎ、最終的な結果が int 型の最大値 INT_MAX を超える場合にも 0 を返すようになっています。この点により、大きな入力に対しても安全に動作します。