题意
给一个排列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<bits/stdc++.h>
#define N 1005
using namespace std;
typedef long long ll;
int n,cnt;
ll ans;
ll p[N],f[N][N];
bool isnotp[N];
template <class T>
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<<ans+1<<endl;
return 0;
}
转载于:https://www.cnblogs.com/Chtholly/p/11543363.html
相关资源：JAVA上百实例源码以及开源项目
