【题解】权值和阶乘

题意

有一个函数，等于各个位上的数字阶乘的乘积。例如。现在给你中的，请你求一个最大的，中不含有，使得。

题解

由于是各个位上的阶乘的乘积。实际上个位数的阶乘可以继续拆解为几个数的阶乘的乘积即有：

f(1)=1!
f(2)=2!
f(3)=3!
f(4)=1*2*3*4=1*2*3*1*2*1*2=3!*2!*2!
f(5)=5!
f(6)=1*2*3*4*5*6=1*2*3*4*5*1*2*3=5!*3!
f(7)=7!
f(8)=1*2*3*4*5*6*7*8=1*2*3*4*5*6*7*1*2*1*2*1*2=7!*2!*2!*2!
f(9)=1*2*3*4*5*6*7*8*9=1*2*3*4*5*6*7*1*2*3*1*2*3*1*2=7!*3!*3!*2!

所以对于给定的数的每一位都可以将其继续拆解，由于要求是最大的数，那么我们拆解完后，对字符串进行从大到小排序即可。

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
const string f[10]= {"0","0","2","3","322","5","53","7","7222","7332"};
int cmp(char x,char y)
{
    return x>y;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        string s;
        string ans;
        cin>>s;
        int n=s.length();
        ans="";
        for(int i=0; i<n; i++)
        {
            if(s[i]-'0'==0||s[i]-'0'==1)
                continue;
            ans=ans+f [s[i]-'0'];
        }
        sort(ans.begin(),ans.end(),cmp);
        cout<<ans<<endl;
    }
    return 0;
}