洛谷 P6280 [USACO20OPEN] Exercise G
题目来源于：洛谷
题目本质：dp，素数筛法，质数
本题与P4161基本一模一样
首先，分析题目发现，某个排列的需要进行恰好 K 步变回原样，这个时候K的值就是这个排序中各个环的长的的最小公倍数(lcm)。然后需要计算所有K的和，就是计算所有符合条件的质数的乘积的和。其次根据唯一分解，一些数的最小公倍数就是除了1以外其它各个数分解质因数后各个质数的最大次幂相乘。最后，枚举每个质数取几个的情况，设dp(i,j)为用了前i 个质数组成的环的长度的和为j 的时候的所有满足条件的K的值。
完整代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e4+5;
int p[N],c[N]; //p[i]表示第i个质数，c[i]表示最多能用几个
ll dp[N][N]; //dp[i][j]前i个物品拼成面值为j
int isp(int x){if(x==1){return 0;}for(int i=2;i*i<=x;i++){if(x%i==0){return 0;}}return 1;
}
int main(){int n,m;int cnt=1;cin>>n>>m;for(int i=2;i<=n;i++){if(isp(i)){p[cnt]=i;c[cnt]=0;int x=i;while(x<=n){c[cnt]++;x*=i; }cnt++; }}memset(dp,0,sizeof(dp));dp[0][0]=1; //将数组初始化 for(int i=1;i<cnt;i++){for(int k=0;k<=n;k++){dp[i][k]=dp[i-1][k];}for(int k=p[i];k<=n;k++){int x=p[i];for(int j=1;j<=c[i]&&x<=k;j++){dp[i][k]=(dp[i][k]+(dp[i-1][k-x]*x)%m)%m; //第i个质用j次,x=p[i]^j x*=p[i]; }} }ll ans=0;for(int i=2;i<=n;i++){ans=(ans+dp[cnt-1][i])%m;}printf("%lld\n",ans+1);return 0;
}