windy 学会了一种游戏。对于 到 这 个数字，都有唯一且不同的 到 的数字与之对应。最开始 windy 把数字按顺序 写一排在纸上。然后再在这一排下面写上它们对应的数字。然后又在新的一排下面写上它们对应的数字。如此反复，直到序列再次变为 。
如： 对应的关系为
windy 的操作如下：
这时，我们就有若干排 到 的排列，上例中有 排。现在 windy 想知道，对于所有可能的对应关系，有多少种可能的排数。
链接
题解
对于一个置换，我们可以将其分解为若干个循环，问题中的「排数」即为这些循环长度的最小公倍数。设这些循环长度分别为
对于某个 的一个质因子 ，它对 有贡献，当且仅当 在 的唯一分解式中的次数是所有 中最大的。
为了便于统计，我们只考虑每个 都是不同的质数的幂的情况（暂不考虑 的情况）
这种情况下，。而 是一组合法的循环长度，当且仅当 。因为我们可以任意添加长度为 的循环，而不对其最小公倍数产生影响，所以 即为合法方案。
现在的问题变成，有一些质数 ，每个质数可以不选，也可以选择一个特定的幂 。要求最终选择的所有数之和 ，求方案总数。这个问题可以转化为分组背包的方案计数问题 —— 第 组物品体积为 （），背包容量为 。
代码
#include <cstdio>
const int MAXN = 1000;
int primes[MAXN], isNotPrime[MAXN + 1], cnt;
inline void getPrimes() {
isNotPrime[0] = isNotPrime[1] = true;
for (int i = 2; i <= MAXN; i++) {
if (!isNotPrime[i]) {
primes[++cnt] = i;
}
for (int j = 1; j <= cnt && i * primes[j] <= MAXN; j++) {
isNotPrime[i * primes[j]] = true;
if (i % primes[j] == 0) break;
}
}
// for (int i = 0; i < cnt; i++) printf("%d\n", primes[i]);
}
int main() {
int n;
scanf("%d", &n);
getPrimes();
static long long f[MAXN + 1][MAXN + 1];
f[0][0] = 1;
for (int i = 1; i <= cnt; i++) {
for (int k = 0; k <= n; k++) f[i][k] = f[i - 1][k];
for (int p = primes[i]; p <= n; p *= primes[i]) {
for (int k = p; k <= n; k++) {
f[i][k] += f[i - 1][k - p];
}
}
// for (int k = 0; k <= n; k++) printf("f[%d][%d] = %d\n", i, k, f[i][k]);
}
long long ans = 0;
for (int i = 0; i <= n; i++) ans += f[cnt][i];
printf("%lld\n", ans);
return 0;
}