SRM-424 250pt: ProductOfDigits

keyword

整数　10進数　C++

問題概要

整数N(<10^9)が与えられる。各桁の数字の積がNに等しくなるような数字のうち、最小の桁数を求める問題。

解法

素因数分解したとき10以上の素数があれば不可能。そうでないときは、桁数を縮めるように8,9,6,4の順で割っていく。

int smallestNumber(int N) {
    if(N==1) return 1;
    int ret=0;
    vector<int> ns;
    while(N%8==0) N/=8, ns.push_back(8);
    while(N%9==0) N/=9, ns.push_back(9);
    while(N%6==0) N/=6, ns.push_back(6);
    while(N%4==0) N/=4, ns.push_back(4);
    while(N%5==0) N/=5, ns.push_back(5);
    while(N%3==0) N/=3, ns.push_back(3);
    while(N%7==0) N/=7, ns.push_back(7);
    while(N%2==0) N/=2, ns.push_back(2);
    if(N!=1) return -1;
    return SZ(ns);
}