SRM424 Div1 Easy ProductOfDigits

2015/05/03 (Sun) SRM 数学

問題

問題文

正の整数 $N$ が与えられる。10 進数表記したときに桁に現れる整数の積が $N$ になるような整数のうち最小のもの $X$ を求め、$X$ の桁数を返しなさい。 そのような整数が存在しない時は $-1$ を返しなさい。

方針

$N$ を10未満の整数の積で表し、昇順に並べたものが $X$ になる。 桁数は小さいほうがいいので大きい数から順に試し割りしていく。 もし積の形に表せないなら $-1$ を返す。

実装

class ProductOfDigits {
public:
    int smallestNumber( int N ) {
        if(N==1) return 1;
        int k = 0;
        for(int i=9;i>=2;i--){
            while(N%i==0){
                k++;
                N/=i;
            }
        }
        return N==1 ? k : -1;
    }
};