题目描述
对于任意输入的正整数n，请编程求出具有n个不同因子的最小正整数m。
例如：n=4，则m=6，因为6有4个不同整数因子1，2，3，6；而且是最小的有4个因子的整数。
输入输出格式
输入格式：
n（1≤n≤50000）
输出格式：
m
输入输出样例
输入样例#1：
INT.IN
4
输出样例#1：
INT.OUT
6
题解：
这道题和[HAOI 2007]反素数ant解题思路和方法简直一毛一样...
同样我们引入这个公式：
对任一整数a＞1，有a=p1a1p2a2…pnan，其中p1<p2<…<pn均为素数，而a1,a2…,an是正整数。
a的正约数个数为：(1+a1)(1+a2)…(1+an)
同理，我们也是求有n个因数的最小整数。
我们最坏的情况所有质数只取1个，由于15<log250000<16
由于数字过大，这里用指数形式保存，用于比较大小
同时注意每层循环枚举取质数的个数时候，因为不合法的情况很多，可以只枚举√n次，然后用枚举的值算出对应的另外一个值。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int len,p[],prime[],n,ans[];
double lg[],maxx=2e9;
void print(int x)
{int i,j,k;
long long s[],Mod=1e4;
memset(s,,sizeof(s));
s[]=;len=;
for (i=;i<=x;i++)
{
for (j=;j<=ans[i];j++)
{
for (k=;k<=len;k++)
{
s[k]=s[k]*prime[i];
}
for (k=;k<=len;k++)
s[k+]+=s[k]/Mod,s[k]%=Mod;
while (s[len+]) len++;
}
}
for (i=len;i>=;i--)
if (i!=len)
printf("%04d",s[i]);
else printf("%d",s[i]);
}
void dfs(double s,int x,int k)
{int i;
if (s>=maxx) return;
if (k==)
{
maxx=s;
memcpy(ans,p,sizeof(ans));
return;
}
if (x>) return;
//cout<<p[x-1]<<endl;
for (i=;(i+)*(i+)<=k;i++)
if (k%(i+)==)
{
if (i!=)
{
p[x]=i;
dfs(s+i*lg[x],x+,k/(i+));
p[x]=;
}
if ((i+)*(i+)!=k)
{
p[x]=k/(i+)-;
dfs(s+p[x]*lg[x],x+,i+);
p[x]=;
}
}
}
int main()
{int i;
cin>>n;
prime[]=;prime[]=;prime[]=;prime[]=;prime[]=;
prime[]=;prime[]=;prime[]=;prime[]=;
prime[]=;prime[]=;prime[]=;prime[]=;
prime[]=;prime[]=;prime[]=;
for (i=;i<=;i++)
lg[i]=(double)log(prime[i]);
dfs(,,n);
//for (i=1;i<=16;i++)
//cout<<ans[i]<<endl;
print();
}