CF1419E Decryption 做题记录

给定一个正整数 $n$，将它的所有大于一的因数按照任意顺序排列在一个环上，你每次可以选择圈上相邻的两个数，在它们中间插入他们的最小公倍数，使得最后的环上不存在两个相邻且互质的数。你需要找到一个需要进行操作次数最少的排列。

$4 \le n \le 10^9$。

容易发现，若 $n=pq$，其中 $p$ 和 $q$ 都是质数，也就是说 $n$ 除了 $1$ 之外只有 $3$ 个因子时，一定需要 $1$ 次操作，否则需要 $0$ 次操作。若 $n=p^k$ 显然直接输出除了 $1$ 外的所有因子即可，否则不难想到一种构造方法：把除了 $1$ 外的因子按照最小质因子分类，每一类放连续一段，两段之间用两个质因子的乘积连接起来。

注意特判只有两类的情况，代码如下：

#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;
}