1025: [SCOI2009]游戏

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1025

问题相当于一个各项之和为N的正整数序列，求所有这样的序列中的各数的最小公倍数有多少种。
设最小公倍数为m，则m=p1^a1*p2^a2...。
而对于一个m，存在一个序列的最小公倍数为m的充要条件是p1^a1+p2^a2+....<=n。
预处理出n以内的质数后，用类似背包Dp的递推统计即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
const int MaxN=1051;

int n,tot=0;
unsigned long long f[MaxN],tmp[MaxN],ans=0;
int ss[MaxN];
bool vis[MaxN];

void treat()
{
    for (int i=2;i<=n;i++)
    {
        if (vis[i]==0)
        {
            ss[tot++]=i;
            vis[i]=1;
        }
        for (int j=0;j<tot && ss[j]*i<=n;j++)
        {
            vis[ss[j]*i]=1;
            if (i%ss[j]==0)
            {
                break;
            }
        }
    }
}

int main()
{
    cin>>n;
    treat();
    f[0]=1;
    for (int i=0;i<tot;i++)
    {
        memcpy(tmp,f,sizeof(f));
        for (int j=ss[i];j<=n;j*=ss[i])
        {
            for (int k=j;k<=n && k-j>=0;k++)
            {
                f[k]+=tmp[k-j];
            }
        }
    }
    for (int i=1;i<=n;i++)
    {
        ans+=f[i];
    }
    cout<<ans+1<<endl;
    return 0;
}

posted on 2013-02-08 23:44 Kiro 阅读(209) 评论(0)  编辑 收藏 引用 所属分类: 衡八oj

只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理