题意

给一个排列1~n，每个数唯一对应的1~n中的一个数，对于一种对应方式，设排列经过k次之后变为原排列，求有多少个不同的k

思路

由于每个数的对应关系唯一，即每个点的出入度都为1，所以如果将对应关系转换为一条有向边，可以构成一张由一些简单环组成的图

如果一个环的大小为c，显然环上的一个点需要走c次才能回到原点，要求每个环上的点同时回到原位，就有\(k=lcm(ci)\)

问题就变成了，将n拆成一些c的和，求有多少个不同的\(lcm(ci)\)

我们发现直接计数会有一些重复的\(lcm\)，于是从去重的角度入手

如：\(lcm(8,18)==lcm(4,9)\)，\(lcm(6,8,15)==lcm(3,8,5)\)，\(lcm(6,5)==lcm(2,3,5)\)

即如果拆出来的数不是质数，那么它们的lcm总是可以选择用质数之间的lcm来替换

另外由于唯一分解定理，如果只拆出质数，对于不同的质数，它们的lcm显然都互不相同

但是如果将n只拆成质数，可能剩下一些，将它们全部拆成1就不会影响当前的lcm了

于是用\(f[i][j]\)表示考虑了前i个质数，且和为j时的情况数，\(ans=\Sigma{f[cnt][i]}\)，其中cnt为质数个数

Code

#include
    
     #define N 1005using namespace std;typedef long long ll;int n,cnt;ll ans;ll p[N],f[N][N];bool isnotp[N];template 
     
      void read(T &x){    char c;int sign=1;    while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;    while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;}void init(int maxn){    isnotp[1]=1;    for(int i=2;i<=maxn;++i)    {        if(!isnotp[i]) p[++cnt]=i;        for(int j=1;j<=cnt&&(ll)p[j]*i<=maxn;++j)        {            isnotp[p[j]*i]=1;            if(i%p[j]==0) break;        }    }}int main(){    read(n);    init(1000);    f[0][0]=1;    for(int i=1;i<=cnt;++i)    {        for(int j=0;j<=n;++j)        {            f[i][j]+=f[i-1][j];            ll sum=p[i];            while(j>=sum)            {                f[i][j]+=f[i-1][j-sum];                sum*=p[i];            }        }    }    for(int i=1;i<=n;++i) ans+=f[cnt][i];    cout<
      
       <