Description：

给定 $n$ ，定义一个置换的排数为 $1$ ~ $n$ 的循环经过这个置换最少 $T$ 次 $(T>0)$ 可以回到原来的序列。求所有可能的排数的数量。

$1\le n \le 1000$

Solution：

首先发现排数就是所有置换的循环节长度的最小公倍数 $+1$ ，于是要求的就是长为 $n$ 的序列中划分成几段的最小公倍数的个数。可以把最小公倍数拆分成许多质数的幂，先筛出来 $n$ 以内所有质数，然后记 $f[i][j]$ 表示前 $i$ 个质数，长为 $j$ 的公倍数个数，转移为 $\begin{align}f[i][j]=\sum_{k=1}^{prime[i]^k\le j}f[i-1][j-k]+f[i-1][j]\end{align}$ ，分别代表在 $lcm$ 中这个质数质数是几，不同指数即有不同 $lcm$ 。

由于没有计算 $1$ ， $dp$ 初值为 $f[0][i]=1$

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 1010

typedef long long ll;

ll f[MAXN][MAXN];

bool isprime[MAXN];

int prime[MAXN],tot = 0;

int main()

{

	scanf("%d",&n);

	for(int i = 2;i <= n;++i)isprime[i] = true;

	for(int i = 2;i <= n;++i)

	{

		if(isprime[i])prime[++tot] = i;

		for(int j = 1;j <= tot && i * prime[j] <= n;++j)

		{

			isprime[i * prime[j]] = false;

			if(i % prime[j] == 0)break;

		}

	}

	for(int i = 0;i <= n;++i)f[0][i] = 1;

	for(int i = 1;i <= tot;++i)

	{

		for(int j = 0;j <= n;++j)

		{

			f[i][j] += f[i - 1][j];

			for(int k = prime[i];k <= j;k *= prime[i])

			{

				f[i][j] += f[i - 1][j - k];

			}

		}

	}

	cout << f[tot][n] << endl;

	return 0;

}