给定一个正整数 ,将它的所有大于一的因数按照任意顺序排列在一个环上,你每次可以选择圈上相邻的两个数,在它们中间插入他们的最小公倍数,使得最后的环上不存在两个相邻且互质的数。你需要找到一个需要进行操作次数最少的排列。
。
容易发现,若 ,其中 和 都是质数,也就是说 除了 之外只有 个因子时,一定需要 次操作,否则需要 次操作。若 显然直接输出除了 外的所有因子即可,否则不难想到一种构造方法:把除了 外的因子按照最小质因子分类,每一类放连续一段,两段之间用两个质因子的乘积连接起来。
注意特判只有两类的情况,代码如下:
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
using namespace std;
const int S=5005;
int n,a[S];
int tot;
map<int,int> idx;
vector<int> vec[S];
int ans[S];
inline void slove()
{
int x;
scanf("%d",&x);
n=0;
for(int i=2;i*i<=x;i++)
{
if(x%i==0)
{
a[++n]=i;
if(i*i!=x) a[++n]=x/i;
}
}
a[++n]=x;
sort(a+1,a+n+1);
idx.clear();
tot=0;
for(int i=1;i<=n;i++)
{
int mxj=1;
bool f=false;
for(int j=2;j*j<=a[i];j++)
{
mxj=j;
if(a[i]%j==0)
{
if(idx.find(j)==idx.end()) idx[j]=++tot;
vec[idx[j]].push_back(a[i]);
f=true;
break;
}
}
for(int j=mxj;j>=1&&!f;j--)
{
if(a[i]%j==0)
{
j=a[i]/j;
if(idx.find(j)==idx.end()) idx[j]=++tot;
vec[idx[j]].push_back(a[i]);
break;
}
}
}
if(tot==1)
{
for(int u:vec[1]) printf("%d ",u);
printf("\n0\n");
}
else if(n==3)
{
for(int i=1;i<=n;i++) printf("%d ",a[i]);
printf("\n1\n");
}
else if(tot==2)
{
int cnt=0;
ans[n]=a[n];
for(int u:vec[1]) if(u!=ans[n]&&u!=vec[1][0]*vec[2][0]) ans[++cnt]=u;
ans[++cnt]=vec[1][0]*vec[2][0];
for(int u:vec[2]) ans[++cnt]=u;
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
printf("\n0\n");
}
else
{
int cnt=0;
ans[n]=vec[1][0]*vec[tot][0];
for(int u:vec[1]) if(u!=ans[n]&&u!=vec[1][0]*vec[2][0]) ans[++cnt]=u;
ans[++cnt]=vec[1][0]*vec[2][0];
for(int i=2;i<tot;i++)
{
for(int u:vec[i]) if(u!=vec[i][0]*vec[i+1][0]) ans[++cnt]=u;
ans[++cnt]=vec[i][0]*vec[i+1][0];
}
for(int u:vec[tot]) ans[++cnt]=u;
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
printf("\n0\n");
}
for(int i=1;i<=tot;i++) vec[i].clear();
}
int main()
{
int T;
scanf("%d",&T);
while(T-->0) slove();
return 0;
}