SRM424 Div1 Easy ProductOfDigits
問題
正の整数 $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;
}
};