可以转化为背包问题。。。。难

/**************************************************************
    Problem: 1025
    User: lxy8584099
    Language: C++
    Result: Accepted
    Time:20 ms
    Memory:9440 kb
****************************************************************/
 
/*
    第一反应是如何构成不同的最小公倍数
    x可以拆分r1^p1*r2^p2*......*rn^pn
    满足  r1^p1+r2^p2+......+rn^pn <=n 即可 
        如果小于n 剩下的都是1个数一组不影响最小公倍数
    f[i][j] 表示前i个质数 前i的singma(ri^pi)为 j的方案数 
     
*/
#include<cstdio>
#define ll long long
using namespace std;
const int N=1050;
ll f[N][N],ans;
int r[N],m,n;
bool vis[N];
void Pre()
{
    for(int i=2;i<=m;i++)
    {
        if(!vis[i]) r[++n]=i;
        for(int j=1;j<=n;j++)
        {
            if(i*r[j]>m) break;
            vis[i*r[j]]=1;
            if(i%r[j]==0) break;
        }
    }
}
void Solve()
{
    scanf("%d",&m);Pre(); 
    for(int i=0;i<=n;i++) f[i][0]=1;  // 全为 1 的情况  
    for(int j=1;j<=m;j++) f[0][j]=1;  // 也是全为 1 的情况 
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            f[i][j]=f[i-1][j];
            for(int k=r[i];k<=m&&j-k>=0;k*=r[i])
                f[i][j]+=f[i-1][j-k];
        }
    }
    printf("%lld\n",f[n][m]);
}
int main()
{
    Solve();
    return 0;
}