codeforce E. Number With The Given Amount Of Divisor

题目链接地址：http://codeforces.com/problemset/problem/27/E

题意：给一个数，求一个最小的正整数，使得它的因子个数为。

分析：与求因子的方法类似，先建立搜索树，以每一个为一层建立树型结构，进行搜索，取最小的

 

以为例进行说明，建树如下： 

 

可以看出从根节点到每一个叶子结点这条路径上的所有数字乘起来都是12的约数，所以12有6个约数。

搜索的思路就明显了，从根节点开始进行深搜，到叶子结点，代码如下：

复制代码 void dfs(int dept,LL ans = 1) { if(dept == cnt) { fac[ct++] = ans; return; } for(int i=0;i<=num[dept];i++) { dfs(dept+1,ans); ans *= pri[dept]; } }

1
2
3
4
5
6
7
8
9
10
11
12
13
void dfs(int dept,LL ans = 1)  
    {  
        if(dept == cnt)  
        {  
            fac[ct++] = ans;  
            return;  
        }  
        for(int i=0;i<=num[dept];i++)  
        {  
            dfs(dept+1,ans);  
            ans *= pri[dept];  
        }  
    }