C++での最小因数分解

正の整数xがあるとすると、各桁の乗算がxに等しい最小の正の整数bを見つける必要があります。そのような答えがない場合は、0を返します。

したがって、入力が48のような場合、出力は68になります

これを解決するには、次の手順に従います-

• ret：=0、mul：=1

• <2の場合：

  • を返す

• 初期化i：=9の場合、i> =2の場合、更新（iを1つ減らす）、実行-

  • mod iは0と同じですが、-

    を実行します。

    • ret：=i * mul + ret

    • mul：=mul * 10

    • a：=a / i

• return（a<2かつret

例

理解を深めるために、次の実装を見てみましょう-

#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