这道题最主要的就是问题的转化，转化完就是一道**题了。

仔细的分析一下，题目中要求“再次出现1,2,3...N的排列”，或者也就是问要进行多少次“置换操作”得到原排列，而我们知道任何置换都是可以写成循环乘积的形式的。

也就是比如对于

1->3
2->4
3->1
4->5
5->2

我们可以化简为

(1 3)(2 4 5)

而对于一个给定置换，问它要多少次才能再次得到原排列，显然只有这个置换分解出的的各个循环的长度是我们关心的。比如对于上例中的置换，我们只需要直到它分解出两个循环，长度为2与3即可断定其只需6次即可得到原排列。也就是所有循环的长度的最小公倍数次。
但这不就是暴力了吗？
但我们可以把循环的长度分解为质数之积，那么所有长度的最小公倍数就是每个质数的最大幂之积。（详见唯一分解定理）
所以我们就可以令dp[n][m]表示从第m个质数往后，值至多为n的方案数，然后dp就好了。

OVER

#include<bits/stdc++.h>
#define ll long long
const int N=1e5+5,INF=0x3f3f3f3f;
using namespace std;

int n,k=1,tmp;
int pri[200]={0,2};
ll ans[N];

inline int read()
{
    register int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

int main()
{
    n=read();
    if(n==1)
    {
        printf("1");
        return 0;
    }
    for(int i=3;i<=n;i+=2)
    {
        pri[++k]=i;
        for(int j=2;j<k;j++)
        {
            if(i%pri[j]==0)
            {
                k--;
                break ;
            }
        }
    }
    ans[0]=1;
    for(int i=1;i<=k;i++)
    {
        for(int j=n;j>=pri[i];--j)
        {
            tmp=pri[i];
            while(tmp<=j)
            {
                ans[j]+=ans[j-tmp];
                tmp*=pri[i];
            }
        }
    }
    ll anss=0;
    for(int i=1;i<=n;i++) anss+=ans[i];
    printf("%lld",anss+1);
    return 0;
}