点击打开链接uva 993

 

题目意思：

给定一个N，能否找到一个自然数Q，满足Q的每一位乘积总和等于N，找到最小的Q并输出，如果没有输出-1

 

解题思路：

1：贪心+暴力枚举所有因子+multiset使用
2:由于数据n最大达到了10^9，那么从0开始枚举是不可能的了，所以我们必须找到一种方法使得这个Q能够快速求出。对于N来说，Q可以有很多个但是最小的永远只有一个，并且Q的每一位都肯定是N的因子，那么我们就想到了一种贪心的思路，如果让N的因子尽量少，并且尽量让小的因子在高位那么得到的值必然会是最小的。所以知道这个思路，就可以开始枚举N的因子，注意要从9-2枚举，把结果存入multiset，最后判断一下容器里面的每一个元素是不是都小于10，是输出这些值，否则输出-1

 

代码：

 

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <set>
using namespace std;

int t , n;
multiset<int>s;
multiset<int>::iterator it ;

bool judge(){
    for(it = s.begin() ; it != s.end() ; it++){
        if(*it >= 10) return false;
    }
    return true;
}

void solve() {
    int i , j , flag; 
    s.clear();
    for(i = n ; i/10 != 0 ;){
        flag = 0;
        for(j = 9 ; j >= 2 ; j--){
            if(!(i%j)){
                s.insert(j) ; i /= j;
                flag = 1 ; break;
            } 
        }
        if(!flag) break;
    }
    s.insert(i);
    if(!judge()) printf("-1\n");
    else{
        
        for(it = s.begin() ; it != s.end() ; it++)
            printf("%d" , *it);
        printf("\n");
    }  
}

int main() {
    //freopen("input.txt" , "r" , stdin);
    scanf("%d%*c" , &t);
    while(t--){
        scanf("%d%*c" , &n);
        if(n >= 10) solve();
        else printf("%d\n" , n);
    }
    return 0;
}