SRM424 Div2 500

前にやってたけど、解きなおした。

問題

整数Nが与えられる。各桁の積がNとなる最小の正の整数Xの桁数を返す。もし存在しなければ-1を返す。

考え方

各桁は2から9までしかありえないので、Nを素因数分解して、それ以上の数値が含まれていれば存在しない。
9->3x3,8->2x2x2,7->7,6->2x3,5->5,4->2x2,3->3,2->2であることを考えて、素因数分解したそれぞれ2,3,5,7の個数を求める。あとは、できる限り数が少なくなるようにそれぞれの数字がいくつ作れるかをカウントしていく。たとえば、2が5個、3が2個なら、9が1個、8が1個、4が1個で答えは3など。