Problem
X是一个n位数的正整数 (𝑥=𝑎0𝑎1...𝑎𝑛−1)
现在定义 F(x)=∏𝑖=0𝑛−1(𝑎𝑖!) ， 比如F(135)=1!3!5!=720.
我们给定一个n位数的整数X(至少有一位数大于1，X中可能有前导0)，
然后我们去找一个正整数(s)符合以下条件：
1.这个数尽可能大，
2.这个数中不能含有数字0或1。
3.F(s)=F(x)
Solution
把2到9阶乘拆开，发现质因子7的时候必选7或8或9，但8和9能拆开，这样数位更多，更优，向下同理，因此拆成2，3，5，7组成的即可。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #include<stdio.h>
#include<set>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<string.h>
#define mem(ss) memset(ss,0,sizeof(ss))
#define rep(d, s, t) for(int d=s;d<=t;d++)
#define rev(d, s, t) for(int d=s;d>=t;d--)
typedef long long ll;
typedef long double ld;
typedef double db;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
ll tp,n;
int sum[7];
int num[7]={2,3,5,7};
int ans[7];
int main(){
io_opt;
cin>>tp>>n;
while(n){
int tmp=n%10;
switch(tmp){
case 2:sum[0]+=1;break;
case 3:sum[0]+=1;sum[1]+=1;break;
case 4:sum[0]+=3;sum[1]+=1;break;
case 5:sum[0]+=3;sum[1]+=1;sum[2]+=1;break;
case 6:sum[0]+=4;sum[1]+=2;sum[2]+=1;break;
case 7:sum[0]+=4;sum[1]+=2;sum[2]+=1;sum[3]+=1;break;
case 8:sum[0]+=7;sum[1]+=2;sum[2]+=1;sum[3]+=1;break;
case 9:sum[0]+=7;sum[1]+=4;sum[2]+=1;sum[3]+=1;break;
default:break;
}
n/=10;
}
ans[3]+=sum[3];
sum[2]-=sum[3];
sum[1]-=sum[3]*2;
sum[0]-=sum[3]*4;
ans[2]+=sum[2];
sum[1]-=sum[2];
sum[0]-=sum[2]*3;
ans[1]+=sum[1];
sum[0]-=sum[1];
ans[0]+=sum[0];
for(int i=3;i>=0;i--){
for(int j=1;j<=ans[i];j++){
cout<<num[i];
}
}
return 0;
}
|