原题链接
题目描述：windy学会了一种游戏。对于1到N这N个数字，都有唯一且不同的1到N的数字与之对应。最开始windy把数字按顺序1，2，3，……，N写一排在纸上。然后再在这一排下面写上它们对应的数字。然后又在新的一排下面写上它们对应的数字。如此反复，直到序列再次变为1，2，3，……，N。 如： 1 2 3 4 5 6 对应的关系为 1->2 2->3 3->1 4->5 5->4 6->6 windy的操作如下 1 2 3 4 5 6 2 3 1 5 4 6 3 1 2 4 5 6 1 2 3 5 4 6 2 3 1 4 5 6 3 1 2 5 4 6 1 2 3 4 5 6 这时，我们就有若干排1到N的排列，上例中有7排。现在windy想知道，对于所有可能的对应关系，有多少种可能的排数。
输入格式：包含一个整数N,1 <= N <= 1000。
输出格式：包含一个整数，可能的排数。
输入样例： 10
输出样例： 16
解析：可以发现，每个置换都有各自的循环节，而最后的排数就是每个循环节长度的lcm+1。 如题目描述中的循环为[1 2 3][4 5][6]。 列数为lcm(3,2,1)+1=6+1=7。 于是题目就转化成了：给定一个数n，将它分为若干个数的和后，求这些数的lcm的种数。 而若干个数的lcm就是这些数相同质因数最大次幂的积。 即\(lcm=p1^{max(c1)}\times p2^{max(c2)}...pn^{max(cn)}\) 若有一个数\(A=p1^{c1}\times p2^{c2},B=p1^{c1},C=p2^{c2}\) 那么显然A对答案的贡献与B和C对答案的贡献是一样的。 而\(B+C<B\times C=A\)，所以可以将A拆成B和C。 于是题目又被转化成了：\(p1^{c1}+p2^{c2}...pn^{cn}=n\)的个数。 而\(p1^{c1}+p2^{c2}...pn^{cn}\)的和不一定要等于n，因为可以单个拆成1，1对lcm没影响。 即求\(p1^{c1}+p2^{c2}...pn^{cn}≤n\)的个数。 于是就可以用背包来解决，设dp[i]表示和为i的数的个数，筛好素数后转移即可。
代码如下：
#include<cstdio> #include<algorithm> #define ll long long using namespace std; const int maxn = 1005; int n, mark[maxn], prim[maxn], tot; ll ans, dp[maxn]; void prepare(int x) { for (int i = 2; i <= x; ++ i) { if (!mark[i]) prim[++ tot] = i; for (int j = 1; j <= tot; ++ j) { if (i * prim[j] > x) break; mark[i * prim[j]] = 1; if (i % prim[j] == 0) break; } } } int main() { scanf("%d", &n); prepare(n); dp[0] = 1; for (int i = 1; i <= tot; ++ i) for (int j = n; j >= prim[i]; -- j) for (int k = prim[i]; k <= j; k *= prim[i]) dp[j] += dp[j - k]; for (int i = 0; i <= n; ++ i) ans += dp[i]; printf("%lld", ans); return 0; }转载于:https://www.cnblogs.com/Gaxc/p/10210790.html
