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

解法： 首先介绍一下约数公式，对于一个给定的整数n = p1^a1*p2^a2*p3^a3…pk^ak。得到n的约数个数为(a1+1)(a2+1)(a3+1)…(ak+1)。可以容易算出这里对答案有贡献的质因数最大为16，我们可以考虑爆搜加剪枝。我们考虑一下如何设计DFS函数。dfs(int x, int y, int z)，x表示搜索到的正整数，y表示x的因数个数，z表示已经搜索到了第z个质数。这样取搜是会T的，我们考虑剪枝，枚举当前质数的指数i时，y%(i+1)==0，那么就是求y的因数，时间复杂度sqrt(y)。还有一个trick是x是会爆long long,怎么办？dfs套高精度？不，我们可以取对数log(n)=Σa[i]*log(pri[i])，就是把约数公式两边同时取自然对数。然后去爆搜就可以了，最后输出答案的时候要用高精度乘法去计算一下然后输出就可以了。 题解参考：http://blog.csdn.net/rlt1296/article/details/53053790