題目鏈接：點擊查看
題目大意：給出一個數 n ，現在需要將其所有大于 1 的因子重新排列成一個首尾相接的環，規定每次操作可以在相鄰兩個位置中加入這兩個數的 lcm，問最少需要操作多少次，才能使得環上所有相鄰的兩個位置都不互質，并輸出最初始的排列
題目分析：可以將所有的數分為兩種情況：
n 由兩個質數相乘得到，如樣例 1 所示，此時直接輸出即可，需要一次操作數其余情況都不需要操作，質因子分解后如下圖所示排列即可
需要注意的是當質因子的個數為 2 時需要特判一下，不然會出現數字重復使用的情況
代碼：
?
//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<unordered_map>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;vector<int>p,fac;map<int,bool>vis;bool is_prime(int n)//試除法判斷質數
{for(int i=2;i*i<=n;i++)if(n%i==0)return false;return true;
}void only(int n)//質因子分解
{p.clear();for(int i=2;i*i<=n;i++)if(n%i==0){p.push_back(i);while(n%i==0)n/=i;}if(n!=1)p.push_back(n);
}void pri(int n)//因數分解
{fac.clear();for(int i=2;i*i<=n;i++)if(n%i==0){fac.push_back(i);if(n/i!=i)fac.push_back(n/i);}fac.push_back(n);
}int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);int w;cin>>w;while(w--){int n;scanf("%d",&n);pri(n);only(n);if(fac.size()==3&&is_prime(p[0])&&is_prime(p[1])){for(int x:fac)printf("%d ",x);puts("\n1");continue;}vis.clear();for(int i=0;i<p.size();i++)vis[p[i]*p[(i+1)%p.size()]]=true;for(int i=0;i<p.size();i++){for(int x:fac)if(x%p[i]==0&&!vis.count(x)){vis[x]=true;printf("%d ",x);}if(p.size()==2&&i==0)continue;printf("%d ",p[i]*p[(i+1)%p.size()]);}puts("\n0");}return 0;
}
?
總結
以上是生活随笔為你收集整理的CodeForces - 1419E Decryption(质因子分解+构造)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
