题解 CF1419E 【Decryption】
pzc2004
2020-09-20 08:43:53
# 题目大意
给定一个正整数 $n$,将它的所有大于一的因数按照任意顺序排列在一个环上,你每次可以选择圈上相邻的两个数,在它们中间插入他们的最小公倍数,使得最后的环上不存在两个相邻且互质的数。你需要找到一个需要进行操作次数最少的排列。
# 题目分析
对于一种排列,容易发现最少需要进行的操作次数就等于该环上相邻且互质的数的对数。所以目标就是最小化相邻且互质的数的对数。
我们先将 $n$ 分解质因数为 $p_1^{a_1}*p_2^{a_2}*...*p_m^{a_m}$。我们可以把 $n$ 的所有因数中被 $p1$ 整除的分为一组,再把剩下的中被 $p2$ 整除的分为一组,一直这样下去,在每组的边界上放能同时被两组的质因数整除的数。
可以发现这样在 $n$ 不是两个不同的质数的乘积时结果一定是0,而在 $n$ 等于两个不同的质数的乘积时结果是1,所以一定是最优的。
代码:
``` cpp
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T &x)
{
x= 0;
char c= getchar();
while(!isdigit(c)) c= getchar();
while(isdigit(c)) x= x * 10 + (c & 15), c= getchar();
}
inline int ksm(int a, int b)//快速幂
{
int s= 1;
for(; b; b>>= 1, a*= a)
if(b & 1) s*= a;
return s;
}
inline int gcd(int a, int b)//最大公约数
{
return b == 0 ? a : gcd(b, a % b);
}
#define N 100001
int n, zys[N], num[N], cnt, ans, b[N], tot;
vector<int> k[N];
inline void fenjie(int n)//分解质因数
{
int m= n;
for(int i= 2; i * i <= n; i++)
{
if(m % i == 0)
{
zys[++cnt]= i, num[cnt]= 0;
while(m % i == 0) m/= i, ++num[cnt];
}
}
if(m > 1)
{
zys[++cnt]= m, num[cnt]= 1;
}
}
inline void dfs(int x, int y, int z)//x表示当前做到哪一个质因数,y表示当前的数,z表示y将要被分到哪一组
{
if(x == cnt + 1)
{
if(y != 1) k[z].push_back(y);//不能有1
return;
}
dfs(x + 1, y, z);
if(z == 0) z= x;
for(int i= 1; i <= num[x]; i++) dfs(x + 1, y * ksm(zys[x], i), z);
}
inline void calc()
{
for(int i= 1; i < tot; i++)
if(gcd(b[i], b[i + 1]) == 1) ++ans;
if(gcd(b[tot], b[1]) == 1) ++ans;
}
signed main()
{
int T;
read(T);
while(T--)
{
read(n), cnt= tot= ans= 0;
fenjie(n);
for(int i= 1; i <= cnt; i++) k[i].clear();
dfs(1, 1, 0);
for(int i= 1; i <= cnt; i++)
{
int x= -1, y= -1;//处理一下每一组的边界
for(int j= 0; j < k[i].size(); j++)
{
if(k[i][j] % zys[((i + cnt - 2) % cnt + cnt) % cnt + 1] == 0)
{
x= k[i][j], k[i].erase(k[i].begin() + j);
break;
}
}
for(int j= 0; j < k[i].size(); j++)
{
if(k[i][j] % zys[i % cnt + 1] == 0)
{
y= k[i][j], k[i].erase(k[i].begin() + j);
break;
}
}
if(x != -1) b[++tot]= x;
for(int j= 0; j < k[i].size(); j++) b[++tot]= k[i][j];
if(y != -1) b[++tot]= y;
}
for(int i= 1; i <= tot; i++) printf("%d ", b[i]);
calc();//计算答案
printf("\n%d\n", ans);
}
return 0;
}
```