很容易发现行数就是lcm环长，也就是要求和为n的若干数lcm的个数

有结论若p1^a1+p2a2+...+pm^{am<=n,则ans=p1}a1*p2^a2*..*pmam是n的一个可行答案。（https://blog.csdn.net/wyfcyx_forever/article/details/40211739有证明

所以我们设f[i][j]为计算了前i个质数，p1^a1+p2a2+...+pi^ai=j的lcm数量，转移的话直接枚举当前新增的p极它的指数加一下即可

#include<iostream>

#include<cstdio>

using namespace std;

const int N=1005;

int n,p[N],tot;

long long f[N][N];

bool v[N];

int main()

{

	scanf("%d",&n);

	v[1]=1;

	for(int i=2;i<=1000;i++)

	{

		if(!v[i])

			p[++tot]=i;

		for(int j=1;j<=tot&&i*p[j]<=1000;j++)

		{

			v[i*p[j]]=1;

			if(i%p[j]==0)

				break;

		}

	}

	for(int i=0;i<=tot;i++)

		f[i][0]=1;

	for(int j=0;j<=n;j++)

		f[0][j]=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=p[i];k<=j;k*=p[i])

				f[i][j]+=f[i-1][j-k];

		}

	printf("%lld\n",f[tot][n]);

	return 0;

}