【20180807模拟测试】t1 function

low逼的我也只能写这样的水题。。。

题面

对于一个整数，定义 f(x)为他的每个数位的阶乘的乘积。例如 f(135)=1! * 3! * 5! =720。给出一个数 a（可以包含前缀零），a 满足他的至少一个数位大于 1。我们要求出最大 的整数 x，其中 x 不含 0 或 1，并且满足 f(a) = f(x)。

【输入】

第一行一个整数 n，表示 a 的长度。 接下来一个整数 a。

【输出】

一行一个整数 x 表示答案。

【输入样例 1】

4

1234

【输出样例 1】

33222

【样例 1 说明】

1! * 2! * 3! * 4! = 3! * 3! * 2! * 2! * 2!

分析

算了吧，你看着我无比整齐的代码会明白的

emm，以下官方正解

统计出质数 2、3、5、7 作为因子出现了多少次。

我们 claim 最后的答案一定由这四个数字构成。（比如考虑 8，还不如 7222）。

我们看看可以放几个 7，能放几个放几个，然后我们就没有 7 了。

我们看看可以放几个 5，能放几个放几个，然后我们就没有 5 了。

我们看看可以放几个 3，能放几个放几个，然后我们就没有 3 了。

最后再把剩下的 2 全放上去。

关于考试时的思路

亲测9！=7！*3！*3！*2！

8！=7！*2！*2！*2！

。。。

以此类推9个数而已3分钟就推完了

反正宁愿要多位数不要大的个位数

哪那么多废话

拆了

然后就只剩2,3,5,7开始拼凑（这和你拆的时候是个反向过程）

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int a[10010],b[1001],n,c[100100],cnt=0;

int main(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++){

       char x;

       cin>>x;

       a[i]=x-'0';

       if(a[i]==2){b[2]++;}

       if(a[i]==3){b[2]++;b[3]++;}

       if(a[i]==4){b[2]+=3;b[3]++;}

       if(a[i]==5){b[2]+=3;b[3]++;b[5]++;}

       if(a[i]==6){b[2]+=4;b[3]+=2;b[5]++;}

       if(a[i]==7){b[2]+=4;b[3]+=2;b[5]++;b[7]++;}

       if(a[i]==8){b[2]+=7;b[3]+=2;b[5]++;b[7]++;}

       if(a[i]==9){b[2]+=7;b[3]+=4;b[5]++;b[7]++;}

    }

    for(int i=7;i>=2;i--){

       while(b[i]>0){

        c[++cnt]=i;

        if(i==2){b[2]--;}

        if(i==3){b[2]--;b[3]--;}

        if(i==4){b[2]-=3;b[3]--;}

        if(i==5){b[2]-=3;b[3]--;b[5]--;}

        if(i==6){b[2]-=4;b[3]-=2;b[5]--;}

        if(i==7){b[2]-=4;b[3]-=2;b[5]--;b[7]--;}

       }

    }

    for(int i=1;i<=cnt;i++)

    printf("%d",c[i]);

    return 0;

}