2015
09-17

# Permutation

A permutation of n elements is a one-to-one function (injection) p: {1,2,…,n} -> {1,2,…,n}. An order of permutation p is the minimal k >= 1, such that for all i=1,2,…,n we have:
p(p(....p(i)...)) = i

That is, p composed with itself k times becomes identity function. For example, the order of the permutation of 3 elements p(1)=3, p(2)=2, p(3)=1 is 2, because p(p(1))=1, p(p(2))=2, p(p(3))=3.
For a given n let us consider permutations of n-elements having the the largest order possible. For example, the maximal order of a permutation of 5 elements is 6. An example of a permutation of 5 elements whose order is 6 is p(1)=4, p(2)=5, p(3)=2, p(4)=1, p(5)=3.
Among all permutations of n elements having the maximal order, we would like to find the earliest one (in a lexycographic order). Being more precise, we say a permutation p of n elements is earlier than a permutation r of n elements, if there is i, such that p(j) = r(j) for all j < i and p(i) < r(i). The earliest permutation of 5 elements having an order 6 is p(1)=2,p(2)=1,p(3)=4,p(4)=5,p(5)=3.

There is one positive integer t (1 <= t <= 30) in the first line of the standard input. In the following T lines there are positive integers N1, N2, …, Nt, one per line, 1 <= ni <= 10000.

There is one positive integer t (1 <= t <= 30) in the first line of the standard input. In the following T lines there are positive integers N1, N2, …, Nt, one per line, 1 <= ni <= 10000.

2
5
14

2 1 4 5 3
2 3 1 5 6 7 4 9 10 11 12 13 14 8

#include<cstdlib>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<list>
#include<queue>
#include<vector>
#define tree int o,int l,int r
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define lo o<<1
#define ro o<<1|1
#define ULL unsigned long long
#define LL long long
#define inf 0x7fffffff
#define eps 1e-7
#define N 10001
using namespace std;
int m,n,T,t,x,y,u;
bool vis[N];
int p[N],pn;
vector<int>g[N];
double d[N];
int ans[N];
void init()
{
for(int i=2; i<N; i++)
{
if(!vis[i])
{
p[pn++]=i;
for(int j=i*i; j<N; j+=i)
vis[j]=1;
}
}
for(int i=0; i<pn; i++)
{
for(int j=N-1; j>=p[i]; j--)
{
double tp=log2(p[i]);
for(int k=p[i],num=1; k<=j; k*=p[i],num++)
if(d[j]<d[j-k]+tp*num)
{
d[j]=d[j-k]+tp*num;
g[j]=g[j-k];
g[j].push_back(k);
}
}
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("ex.in","r",stdin);
#endif
init();
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int sum=0,m=0;
for(int i=0; i<g[n].size(); i++)
{
sum+=g[n][i];
ans[m++]=g[n][i];
}
for(int i=sum; i<n; i++)
ans[m++]=1;
sort(ans,ans+m);

int f=0,t=1;
for(int i=0; i<m; i++)
{
for(int j=0; j<ans[i]-1; j++)
{
if(f)putchar(' ');
printf("%d",t+j+1);
f=1;
}
if(f)putchar(' ');
printf("%d",t);
f=1;
t+=ans[i];
}
puts("");
}

return 0;
}