Description

对于任意输入的正整数n，请编程求出具有n个不同因子的最小正整数m。例如：n=4，则m=6，因为6有4个不同整数因子1，2，3，6；而且是最小的有4个因子的整数。

Input

n（1≤n≤50000）

Output

m

Sample Input

4

Sample Output

6

HINT

Source

 

题解

考虑这道题我们首先要知道

知道了这个定理后，我们不难发现可以将n分解质因数，且最多有16个质因子

这样我们可以dfs(now,nowx,s)//now表示当前取到第now个质数，nowx表示当前数，s表示对数（可以发现最后的答案是会超过long long的，所以我们存一下对数）

但是裸的dfs是会T的，需要最小值的剪枝优化

最后用高精度算一下就可以了

1 #include
      
        2 #define N 50005 3 using namespace std; 4 const int prime[17]={
    0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53}; 5 int n,cnt,num,len,k; 6 int a[N]; 7 int t[10000]; 8 int tmp[20],b[20]; 9 double Min;10 double lg[20];11 void mul(int x){12     for (int i=1;i<=len;i++) t[i]=t[i]*x;13     int j=1;14     while (t[j]>9||j
       
        =Min) return;23     if (nowx==1){24         Min=s; k=now-1;25         for (int i=1;i<=now-1;i++) b[i]=tmp[i];26         return;27     }28     if (now>16) return;29     for (int i=0;(i+1)*(i+1)<=nowx;i++)30         if (!(nowx%(i+1))){31             if (i){32                 tmp[now]=i;33                 dfs(now+1,nowx/(i+1),s+tmp[now]*lg[now]);34             }35             if ((i+1)*(i+1)!=nowx){36                 tmp[now]=nowx/(i+1)-1;37                 dfs(now+1,i+1,s+tmp[now]*lg[now]);38             }39         }40 }41 int main(){42     for (int i=1;i<=16;i++) lg[i]=log(prime[i]);43     scanf("%d",&n);44     Min=1e9;45     dfs(1,n,0);46     t[1]=1; len=1;47     for (int i=1;i<=k;i++){48         int p=prime[i];49         for (int j=1;j<=b[i];j++) mul(p);50     }51     for (int i=len;i>=1;i--)52         printf("%d",t[i]);53     return 0;54 }