Description
一个关于n个元素的排列是指一个从{1, 2, …, n}到{1, 2, …, n}的一一映射的函数。这个排列p的秩是指最小的k，使得对于所有的i = 1, 2, …, n，都有p(p(…p(i)…)) = i（其中，p一共出现了k次）。 例如，对于一个三个元素的排列p(1) = 3, p(2) = 2, p(3) = 1，它的秩是2，因为p(p(1)) = 1, p(p(2)) = 2, p(p(3)) = 3。 给定一个n，我们希望从n!个排列中，找出一个拥有最大秩的排列。例如，对于n=5，它能达到最大秩为6，这个排列是p(1) = 4, p(2) = 5, p(3) = 2, p(4) = 1, p(5) = 3。 当我们有多个排列能得到这个最大的秩的时候，我们希望你求出字典序最小的那个排列。对于n个元素的排列，排列p的字典序比排列r小的意思是：存在一个整数i，使得对于所有j < i，都有p(j) = r(j)，同时p(i) < r(i)。对于5来说，秩最大而且字典序最小的排列为：p(1) = 2, p(2) = 1, p(3) = 4, p(4) = 5, p(5) = 3。
Input
输入的第一行是一个整数T（T <= 10），代表数据的个数。 每个数据只有一行，为一个整数N。
Output
对于每个N，输出秩最大且字典序最小的那个排列。即输出p(1), p(2),…,p(n)的值，用空格分隔。
Sample Input
2 5 14
Sample Output
2 1 4 5 3 2 3 1 5 6 7 4 9 10 11 12 13 14 8
Data Constraint
对于40%的数据，有1≤N≤100。 对于所有的数据，有1≤N≤10000。
分析
稍作分析就可以发现这是要把一个正整数分为多个正整数，其最小公倍数最大的正整数组的最小字典序
考虑到排列很难构造，那我们直接构造最小公倍数
它必定是若干个质数的乘积
那么题中的最小公倍数则可以表示为
W=p1^c1*p2^c2*p3^c3…… p是质数 c是质数的指数,p之和不超过n
如果比n小怎么办？直接在排列最前端补足1 2 3 4 5 6……
那么可得f[i][j]为处理了第i个质数，和为j的最大最小公倍数（因为是质数直接乘）
f[i][j]=f[i-1][j-w]*w w为质数或质数的幂
至于答案，只需要用g[i][j]记录一下状态是从哪个状态转移过来的即可
注意，f的值会非常大，可以用自然对数法，也可以直接用double（本题几乎无视精度问题）
#include#include #include using namespace std;typedef double ld;const int N=1e4+10;int prime[1310],cnt;bool b[N];int t,n;int from[1310][N],cunt,a[1310],acnt;ld f[1310][N],mx; void Get_Prime() { for (int i=2;i<=10000;i++) { if (!b[i]) prime[++cnt]=i; int j=2*i; while (j<=10000) { b[j]=1; j+=i; } }}void Get(int last) { int dep=cnt; while (dep) { if (last-from[dep][last]) a[++acnt]=last-from[dep][last]; last=from[dep][last];dep--; }}int main() { Get_Prime(); for (scanf("%d",&t);t;t--) { scanf("%d",&n); if (n<5) { for (int i=2;i<=n;i++) printf("%d ",i); printf("1\n"); continue; } mx=0; for (int i=1;i<=cnt;i++) for (int j=0;j<=n;j++) f[i][j]=0; f[0][0]=1; for (int i=1;i<=cnt;i++) { int l=prime[i]; for (int j=0;j<=n;j++) f[i][j]=f[i-1][j],from[i][j]=j; for (;l<=n;l*=prime[i]) { for (int j=l;j<=n;j++) if (f[i][j]