原文链接http://www.cnblogs.com/zhouzhendong/p/8990592.html
题目传送门 - CodeForces 516A
题意
对于一个正整数$x$，$f(x)=x$各个数位的阶乘之积。
给定一个数$a$，满足$f(a)>1$，求一个最大的不含有$0$或者$1$的$x$满足$f(x)=f(a)$。
$a<10^{16}$
题解
我们将$f(a)$分解质因数并统计各个质因数个数作为状态。
首先考虑到每一个数位都是$2$~$9$的，质因数只可能有$4$种。
而且，即便是贡献最大的$9$，也只会贡献$7$个质因数$2$、$4$个质因数$3$、$1$个质因数$5$和$1$个质因数$7$。
考虑到$a$最多只有$15$位，所以质因数$2,3,5,7$的总个数最多分别为$105,60,15,15$。
我们用$dp[s2][s3][s5][s7]$来表示$f(x)=2^{s2}3^{s3}5^{s5}7^{s7}$的最大$x$。
显然这个$x$会很大，为了避免写高精度，我们可以这样考虑：
由于我们只需要知道$x$分别由几个$2$、几个$3$、…、几个$9$组成，就可以唯一确定一个最大的$x$。（按照顺序从大到小）
所以，我们考虑换一种储存方式。考虑到$2$最多只有$105$个，所以我们可以给每一个数字$7$个二进制位（事实上我代码里只有$6$位压缩也过了），每$7$个二进制位里面保存着他所代表的数的个数信息。由于只需要保存$8$个数字的信息，所以总共需要$56$个二进制位，开$64$位整型即可。至于比较大小，太简单不多说。
然后，对于当前状态，从$2$到$9$枚举之前放了哪一个数字，然后根据之前的转移即可。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=20,S2=105,S3=60,S5=15,S7=15;
int n,tot[4];
LL dp[S2+1][S3+1][S5+1][S7+1];
int lists[N][4]={
{0,0,0,0},
{0,0,0,0},
{1,0,0,0},
{0,1,0,0},
{2,0,0,0},
{0,0,1,0},
{1,1,0,0},
{0,0,0,1},
{3,0,0,0},
{0,2,0,0}
};
char s[N];
int cntd(LL x){
int tot=0;
for (int i=9;i>=2;i--)
tot+=x&63LL,x>>=6;
return tot;
}
bool bigger(LL a,LL b){
int c1=cntd(a),c2=cntd(b);
if (c1!=c2)
return c1>c2;
for (int i=9;i>=2;a>>=6,b>>=6,i--)
if ((a&63LL)!=(b&63LL))
return (a&63LL)>(b&63LL);
return 0;
}
int main(){
scanf("%d%s",&n,s);
for (int i=2;i<=9;i++)
for (int j=0;j<4;j++)
lists[i][j]+=lists[i-1][j];
memset(tot,0,sizeof tot);
for (int i=0;i<n;i++)
for (int j=0;j<4;j++)
tot[j]+=lists[s[i]-'0'][j];
memset(dp,-1LL,sizeof dp);
dp[0][0][0][0]=0;
for (int s2=0;s2<=tot[0];s2++)
for (int s3=0;s3<=tot[1];s3++)
for (int s5=0;s5<=tot[2];s5++)
for (int s7=0;s7<=tot[3];s7++)
for (int i=2;i<=9;i++){
int t2=s2-lists[i][0];
int t3=s3-lists[i][1];
int t5=s5-lists[i][2];
int t7=s7-lists[i][3];
if (t2<0||t3<0||t5<0||t7<0)
continue;
if (dp[t2][t3][t5][t7]==-1)
continue;
LL now=dp[t2][t3][t5][t7]+(1LL<<((9-i)*6));
if (dp[s2][s3][s5][s7]==-1||bigger(now,dp[s2][s3][s5][s7]))
dp[s2][s3][s5][s7]=now;
}
LL x=dp[tot[0]][tot[1]][tot[2]][tot[3]];
for (int i=9;i>=2;i--,x>>=6)
for (int j=0;j<(x&63LL);j++)
putchar('0'+i);
return 0;
}