[SCOI2009]游戏

读完题我们可以分成两部分。
第一部分是把n拆成由数字1~n组成的不同排列。
如3=1+1+1
3=2+1
3=3
第二部分是：排列中每个数的最小公倍数。
每个排列的最小公倍数去重后的个数是答案。
对于第二部分，我们想一想，可以发现，最小公倍数可以分为多个质因数。
所以对于第一部分，我们要用n以下的质数组成n的排列。
将两部分结合起来就是用n以下的素数的无限背包。

#include<cstdio>
#include<cstring>
#define ll long long
const int M=1010;
ll f[M];//f[j]为和为j的不同排数 
int n,len=0;

int p[M],v[M];

void prim()
{
    memset(v,0,sizeof(v));
    for(int i=2;i<=M;i++)
    {
        if(v[i]==0)v[i]=i,p[++len]=i;
        for(int j=1;j<=len && p[j]<=v[i] &&(p[j]*i<=M);j++)
        v[i*p[j]]=p[j];
    }
}

int main()
{
    scanf("%d",&n);
    prim();
    memset(f,0,sizeof(f));
    f[0]=1ll;
    for(int i=1;i<=len&&p[i]<=n;i++)
    {
        for(int j=n;j>=p[i];j--)
        {
            int x=p[i];//printf("%d\n",p[i]);
            while(x<=j)f[j]+=f[j-x],x*=p[i];//防止重复计算
        }
    }
    ll ans=1ll;
    for(int i=1;i<=n;i++)ans+=f[i];
    printf("%lld",ans);
    return 0;
}