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
|
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <cmath>
using namespace std;
typedef long long ll;
double f[20][50005],P_[20];
int F[20][50005]={0},n,P[17]={1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
int real_ans[50005]={0};
int (int s1[],int s2){
int i,j,x=0;
for(i=1;i<=s1[0];i++)
x+=s1[i]*s2,
s1[i]=x%10000,x/=10000;
while(x)
s1[++s1[0]]=x%10000,x/=10000;
}
int main(){
scanf("%d",&n);
int i,j,k,mini,cnt;
double m,ans;
for(i=0;i<20;i++)
for(j=0;j<=n;j++)
f[i][j]=1e9;
for(i=0;i<=16;i++)
P_[i]=log(P[i]);
for(i=1;i<=n;i++)
f[1][i]=(i-1)*P_[1],F[1][i]=1;
for(i=1;i<=15;i++)
for(j=1;j<=n;j++)
for(k=1;j*k<=n;k++){
m=f[i][j]+(k-1)*P_[i+1];
if(m<f[i+1][j*k])
f[i+1][j*k]=m,F[i+1][j*k]=j;
}
for(ans=1e9,i=1;i<=16;i++)
if(ans>f[i][n])
ans=f[i][n],mini=i;
real_ans[0]=real_ans[1]=1;
for(j=mini,k=n;j>0;j--){
cnt=k/F[j][k];
for(i=1;i<cnt;i++)
multiply_to_int(real_ans,P[j]);
k=F[j][k];
}
printf("%d",real_ans[real_ans[0]]);
for(i=real_ans[0]-1;i>=1;i--)
printf("%04d",real_ans[i]);
printf("n");
return 0;
}
|
近期评论