codeforce E. Number With The Given Amount Of Divisor

80 阅读 0 评论 53 点赞

我是靠谱客的博主优美水壶，最近开发中收集的这篇文章主要介绍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];  
        }  
    }