首先这题的本质就是把(n)分成若干个数的和，求他们的(lcm)有多少种情况
然后据说有这么个结论：若(p_1^{c_1}+p_2^{c_2}+...+p_m^{c_m}leq n)，则(ans=p_1^{c_1}p_2^{c_2}...p_m^{c_m})就是一个可行的(lcm)
证明我不会，可以看这里
然而总感觉上面的证法有哪里不太对……
不管了反正总之dp就可以了
//minamoto
#include<bits/stdc++.h>
#define ll long long
#define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i)
using namespace std;
const int N=1000;
int p[N],m,n;bool vis[N+5];ll f[205][N+5];
void init(){
fp(i,2,N){
if(!vis[i])p[++m]=i;
for(register int j=1;j<=m&&i*p[j]<=N;++j){
vis[i*p[j]]=1;
if(i%p[j]==0)break;
}
}
}
int main(){
// freopen("testdata.in","r",stdin);
scanf("%d",&n),init();
fp(i,0,m)f[i][0]=1;fp(i,1,n)f[0][i]=1;
fp(i,1,m)fp(j,1,n){
f[i][j]=f[i-1][j];
for(register int k=p[i];k<=j;k*=p[i])
f[i][j]+=f[i-1][j-k];
}printf("%lld
",f[m][n]);return 0;
}