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。
题解
别看题意那么长，实际浓缩起来很短：
给你个n把n分成很多的数加起来，并且使得这些数的lcm最大。
然后把这n个数从小到大循环输出一下即可。
依照这个题意，我们考虑先把lcm求出来后找答案。
我们发现，选择质因数比选择其他的数求出来的lcm更大。
所以我们就有了方向——考虑质数。
利用dp，设表示当且选择到第个质数，选出来的数加起来为的最大lcm。
如何转移？
我们发现，其实选择质数的幂也是可以的。因此我们在枚举，的同时，枚举一个表示当且质数的幂。
设
方程即为：
但是这样求出来的f非常大，longlong存不下。
可以考虑自然对数或double。（美妙的实数）
当我们求出lcm最大值后，我们直接把它质因数分解很麻烦。
怎么办？我们发现在dp的过程中已经是利用质因数来搞了。
所以在dp的时候记录一下当且状态由那个状态得来即可。
随便搞搞。
标程
var
i,j,k,l,n,m,t:longint;
zs:array[0..10000] of longint;
bz:array[1..10000] of boolean;
f:array[0..1230,0..10000] of double;
fr:array[0..1230,0..10000,0..2] of longint;
len:array[1..10000] of longint;
procedure dg(i,j:longint);
begin
if fr[i,j,2]>0 then
begin
dg(fr[i,j,1],fr[i,j,2]);
end;
//else
begin
inc(m);
len[m]:=fr[i,j,0];
end;
end;
begin
//assign(input,'0data.in');reset(input);
for i:=2 to 10000 do
begin
if not bz[i] then
begin
inc(zs[0]);
zs[zs[0]]:=i;
for j:=1 to 10000 div i do
begin
bz[i*j]:=true;
end;
end;
end;
f[0,0]:=1;
for i:=1 to 10000 do
begin
f[0,i]:=1;
fr[0,i,0]:=1;
fr[0,i,1]:=0;
fr[0,i,2]:=i-1;
end;
for i:=1 to zs[0] do
begin
for j:=0 to 10000 do
begin
if f[i,j]<f[i-1,j] then
begin
f[i,j]:=f[i-1,j];
fr[i,j,0]:=fr[i-1,j,0];
fr[i,j,1]:=fr[i-1,j,1];
fr[i,j,2]:=fr[i-1,j,2];
end;
end;
for j:=1 to 10000 do
begin
l:=1;
for k:=1 to 10000 do
begin
l:=l*zs[i];
if j>=l then
begin
if f[i-1,j-l]*l>f[i,j] then
begin
f[i,j]:=f[i-1,j-l]*l;
fr[i,j,0]:=l;
fr[i,j,1]:=i-1;
fr[i,j,2]:=j-l;
end;
end
else
break;
end;
end; {
for j:=1 to 10000 do
begin
if f[i+1,j]<f[i,j] then
begin
f[i+1,j]:=f[i,j];
fr[i+1,j,0]:=fr[i,j,0];
fr[i+1,j,1]:=fr[i,j,1];
fr[i+1,j,2]:=fr[i,j,2];
end;
end; }
end;
readln(t);
while t>0 do
begin
dec(t);
readln(n);
m:=0;
j:=0;
//inc(m);
//len[m]:=fr[zs[0],n,0];
dg(zs[0],n);
for i:=1 to m do
begin
for j:=i+1 to m do
begin
if len[i]>len[j] then
begin
k:=len[i];
len[i]:=len[j];
len[j]:=k;
end;
end;
end;
j:=0;
for i:=1 to m do
begin
l:=j+1;
for k:=2 to len[i] do
begin
inc(l);
write(l,' ');
end;
write(j+1,' ');
j:=j+len[i];
end;
writeln;
end;
end.
end.