d418: 00993 - Product of digits

http://luckycat.kshs.kh.edu.tw/homework/q993.htm

https://zerojudge.tw/ShowProblem?problemid=d418

題目大意:給出一個正整數， 要求找到一個自然數，使得該自然數的每一位的數字的乘積等於正整數。並且要求最小，不存在輸出-1.

解題思路：將正整數分解因子，注意這裡要從9開始， 因為要求值最小，即對應的位數也要最小，所以分解的的因子要盡量最大， 但是不能超過9，10以上是兩位數。

1是比較特殊的情況， 因為終止條件是n == 1和i < 2, 所以一開始就要處理掉1的情況，單獨考慮， 然後當因子全部分解完之後，n 仍然不等1，說明不能完全分解成2 ~9之間的因子，輸出-1.

#include <iostream>
#include <algorithm>
using namespace std;

const int Max = 40;
int num[Max] = {0};//記錄N的所有因數

int main () {

    int n, N, cnt;

    cin>>n;//n比測資

    while (n--) {

        cin>>N;

        cnt = 0; //N是用cnt個個位數字相乘

        if (N != 1) {

            //拿 9~2 來做因式分解，因為N只允許用個位數字當因數
            for (int i = 9; i > 1; i--) {

                while (N % i == 0) {
                    num[cnt++] = i;
                    N = N / i;
                }

                //N已被分解完成，提早跳出
                if (N == 1) break;

            }

            //陣列是由大到小，所以要轉成由小到大
            sort(num, num + cnt);

            if (N != 1){
                //找不到
                cout<<"-1"<<endl;
            }
            else {
                //找到了
                for (int i = 0; i < cnt; i++)
                   cout<<num[i];
                cout<<endl;
            }
        }
        else{
            //如果N=1的話，特例處理
            cout<<"1"<<endl;
        }

    }
    return 0;
}