开放原子开发者工作坊

URAL_1014

    基本的贪心思路是留下尽量少的项，而且这些项的字典序尽可能小。因此，要优先生成8，然后优先生成9，6，4，最后生成质数。至于为什么先生成9，再生成6，再生成4，这个可以将2、3的个数分奇偶讨论一下就很清楚了。

    此外还有一些细节需要注意，比如N=1的时候输出1，N=0的时候输出10。

#include<stdio.h>
#include<string.h>
int N, h[15];
void solve()
{
    int i;
    memset(h, 0, sizeof(h));
    while(N % 8 == 0)
        ++ h[8], N /= 8;
    while(N % 9 == 0)
        ++ h[9], N /= 9;
    while(N % 6 == 0)
        ++ h[6], N /= 6;
    while(N % 4 == 0)
        ++ h[4], N /= 4;
    for(i = 2; i < 8; i ++)
        while(N % i == 0)
            ++ h[i], N /= i;
    if(N != 1)
        printf("-1");
    else
    {
        for(i = 2; i < 10; i ++)
            while(h[i])
                printf("%d", i), -- h[i];
    }
    printf("\n");
}
int main()
{
    while(scanf("%d", &N) == 1)
    {
        if(N == 0)
            printf("10\n");
        else if(N == 1)
            printf("%d\n", N);
        else
            solve();
    }
    return 0;
}