频道栏目
首页 > 考试 > 其他 > 正文
caioj1043: [视频]递归13(因式分解【深搜+剪枝 或 DP 】)
2017-09-12 10:38:45      个评论    来源:OZY的博客  
收藏   我要投稿

【题意】
分解一个整数n,格式如下:
n = a1*a2*a3*a4…….*am
比如:
12=12
12=6*2
12=4*3
12=3*4
12=3*2*2
12=2*6
12=2*3*2
12=2*2*3
总共8种

【输入格式】
一行一个整数n(1 < n < = 2^31 )。
【输出格式】
输出分解的总数。
【样例输入】
12
【样例输出】
8

输入
输出
样例输入
12
样例输出
8

感想

一开始看错题了QAQ
然后之前一直很吵,没静下来思考。。
于是做了很久。。
还想了一个不靠谱的DP
真的该反省一下自己了,觉得这题很简单,就没有认真的思考就做题。。
这样肯定是错误的。。

以后无论遇到什么题都要认真思考!!

题解

其实就是一个辣鸡的dfs,然后要加记忆化
时间复杂度是sqrtn的

然后由于数据太水,我就加强了数据。。
但是A的人较多,就不重判了

#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
map tt;
LL ans=0;
LL n;
LL dfs (LL x)
{
    if (tt[x]!=0) return tt[x]; 
    tt[x]=1;
    if (x==1) return 0;
    for (LL u=2;u*u<=x;u++)
    {
        if (x%u==0)
        {
            tt[x]+=dfs(x/u);
            if (u*u!=x) tt[x]+=dfs(u);
        }
    }
    return tt[x];
}
int main()
{
    tt.clear();
    scanf("%lld",&n);
    printf("%lld\n",dfs(n));
    return 0;
}
点击复制链接 与好友分享!回本站首页
上一篇:bzoj3527: [Zjoi2014]力
下一篇:HDU 6198 number number number 题解
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站