很巧妙的变形...大概cf也有很多,这个题首先是一个排列的关系可能会形成1~n个环..
然后就是问你环的大小的lcm,这个可以转化,我们知道lcm可以写成每个质因数的乘积.
又有个巧妙的转化了,因为1的存在.我们可以任意分配质因子个数,这样是不影响方案数的(因为到了最后也最多这个值,其他值也会被包含)...如此这个题就完美的解决了.先预处理n的素数,然后用01背包进行转移即可.

#include <bits/stdc++.h>
using namespace std;
const int N=1005;
int pr[N],st[N],n;
long long f[N];
void init()
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])   { st[i]=1; pr[++pr[0]]=i;}
        for(int j=1;pr[j]*i<=n;j++)
        {
            st[pr[j]*i]=1;
            if(i%pr[j]==0) break;
        }
    }
}//欧拉筛都忘了,呜呜呜...就是拿最小质因子来筛取合数.

int main()
{
    long long ans=0;
    scanf("%d",&n);
    f[0]=1;
    init();
    for(int i=1;i<=pr[0];i++)
    {
        for(int j=n;j>=pr[i];j--)
        {
            int temp=pr[i];
            while(j>=temp) f[j]+=f[j-temp],temp*=pr[i];
        }
    }
    for(int i=0;i<=n;i++) ans+=f[i];
    printf("%lld\n",ans);
    return 0;
}