LINK：求正整数
比较难的高精度。
容易想到贪心不过这个贪心的策略大多都能找到反例。
考虑dp.
f[i][j]表示前i个质数此时n的值为j的最小的答案。
利用高精度dp不太现实。就算上FFT也会T掉。
乘积的形式 我们可以将其变成对数的形式就很容易转移了。
转移时记录决策 然后 最后做一遍高精度即可。
值得一提的是 压位高精度时比如压15为那么最后输出的形式为printf("%015d",ans);
因为%1e15之后有效数位还有15个而并非14个.
const int MAXN=510,N=17;
int n,m,top;
db c[N];
db f[N][MAXN];
int g[N][MAXN],v[MAXN];
int a[N]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
int w[MAXN];
int ans[MAXN*10],len;
inline void get_path(int i,int j)
{
int las=g[i][j];
int ww=v[las]/v[j];
w[i]=ww-1;
if(i)get_path(i-1,las);
}
int main()
{
//freopen("1.in","r",stdin);
//freopen("2.out","w",stdout);
get(n);m=16;if(n==1){puts("1");return 0;}
rep(1,m,i)c[i]=log(a[i]*1.0);
rep(1,n,i)if(n%i==0)v[++top]=i;
rep(0,m,i)rep(1,top,j)f[i][j]=INF;
f[0][top]=0;
rep(0,m-1,i)
{
//if(i==m-1)cout<<"ww"<<endl;
rep(1,top,j)
{
//cout<<f[i][j]<<endl;
//if(i==m-1&&j==top)cout<<"ww"<<' '<<f[m-1][j]<<endl;
if(fabs(f[i][j]-INF)<=EPS)continue;
for(int k=1;k<=j;++k)
{
if(v[j]%v[k]==0)
{
int w=v[j]/v[k];
//if(i==m-1&&j==top&&k==1)
//cout<<' '<<f[i+1][k]<<' '<<f[i+1][k]-f[i][j]-c[i+1]*(w-1)<<endl;
if(f[i+1][k]-f[i][j]-c[i+1]*(w-1)>EPS)
{
f[i+1][k]=f[i][j]+c[i+1]*(w-1);
//if(i+1==m)cout<<f[i+1][k]<<endl;
g[i+1][k]=j;
}
}
}
}
}
//cout<<f[2][1]<<' '<<f[3][1]<<f[1][1]<<endl;
get_path(m,1);
//rep(1,m,i)put(w[i]);
//w[1]=100;w[3]=100;
ans[len=0]=1;
rep(1,m,i)
{
while(w[i])
{
rep(0,len,j)ans[j]=ans[j]*a[i];
rep(0,len,j)ans[j+1]+=ans[j]/mod,ans[j]%=mod;
if(ans[len+1])++len;--w[i];
}
}
printf("%d",ans[len]);
fep(len-1,0,i)printf("%06d",ans[i]);
return 0;
}