TopCoder SRM 424 Div1 Easy ProductOfDigits

問題

各桁の積がnに等しいような数Xのうち、桁数最小のものの桁数を求めよ。
そのような数Xが存在しないときは-1を返せ。

制約条件

n≦10^9

方針

nを素因数分解する。
nが11以上の素因数を持つとき、どんな数Xの各桁の積もnに等しくなることはないので、-1を返す。

そうでないときは、必ずXが存在する。
Xの最小の桁数を求めたい。

5以上の素因数は、他の数と組にすることができないのでそれ一つで一桁を使う。
3は他の2一個または3一個と組にできる。
貪欲に3同士をペアにして、最後に余った3を（できるなら）2とペアにしてやる。
2は3つまでペアにできるので、できるだけペアにする。

ソースコード

class ProductOfDigits {
  public:
  int smallestNumber(int N) {
    if(N==1)return 1;
    map<int,int> f;
    for(int i=2;i*i<=N;i++)if(N%i==0){
      int c=0;
      while(N%i==0)N/=i, c++;
      f[i]=c;
    }
    if(N>1)f[N]=1;
    int two=f[2], three=f[3], five=f[5], seven=f[7];
    fr(i,f)if(i->first>7)return -1;
    int ans=five+seven;
    ans+=three/2;
    ans+=three%2; two-=three%2;
    ans+=(two+2)/3;
    return ans;
  }
};