注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 1025  

2013-02-05 13:09:49|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1025题意看了好久才明白……

不就是要你求:把一个数n拆分成若干个数,问这若干个数的最小公倍数的可能情况吗?

水题……联赛前的模拟赛考过,

DP

筛素数表,F[i][j]表示j拆分的若干个数分解质因数之后最大质因数不超过第i个质因数的最小公倍数可能性。

F[i][j]=F[i-1][j]+sigma{F[i][j-p[i]^k]}

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 1010
using namespace std;
typedef long long LL;
LL F[MAXN][MAXN];
int n,prime[MAXN],tot;
bool mark[MAXN];
void ptm()
{
    for(int i=2;i<=1000;i++)
    {
        if(mark[i]==false)  prime[++tot]=i;
        for(int j=1;j<=tot&&prime[j]*i<=1000;j++)
        {
            mark[prime[j]*i]=true;
            if(i%prime[j]==0)  break;
        }
    }
}
void Dp()
{
    for(int i=0;i<=tot;i++)
        F[i][0]=1;
    for(int i=1;i<=n;i++)
        F[0][i]=1;
    for(int i=1;i<=tot;i++)
        for(int j=1;j<=n;j++)
        {
            F[i][j]=F[i-1][j];
            for(int k=prime[i];k<=j;k*=prime[i])
                F[i][j]+=F[i-1][j-k];
        }
}
int main()
{
    scanf("%d",&n);
    ptm();
    Dp();
    printf("%lld\n",F[tot][n]);
    return 0;
}


  评论这张
 
阅读(797)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017