CF #671 (Div. 2) 部分

忘打了QAQ

E.Decryption

题意：

给你一个合数$n$，要你自己得出其所有大于1的因子，然后将这些因子排成一个环，使得任意两个相邻的数都不互质，若无法得到，可以花费$1cost$，在两个互质的数中间插入他们的$lcm$，问怎样排列才能使得$cost$最小。

题解：

由唯一分解定理我们可以知道，对于任意一个合数$n$，有：

$n=p_1^{c_1}p_2^{c_2}p_3^{c_3}\dots p_k^{c_k}$

则我们只需要把数排成如下形式即可：

$p_1\dots p_1\times j\dots p_1\times p_2\ p_2\dots p_2\times j\dots p_2\times p_3\ p_3\dots p_{k-1}p_{k}\ p_k\dots p_k\times j \dots$

注意一下只有三个因子的，如果较小的两个因子互质要输出$1$，否则输出$0$。

其他的情况只要构造即可，无论如何都可以构造成两两不互质。

ps：代码比较繁琐，感觉很多地方可以优化掉

AC代码：

//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define EB emplace_back
#define IN insert
#define CT count
#define _for(i,a,b) for(int i = (a);i<(b);++i)
#define endl '\n'
using namespace std;
typedef long long ll;


map<int,bool>mp;
signed main() {
  FIO;
  int T;cin>>T;
  while(T--){
    mp.clear();
    vector<int>p,pp;
    int n;cin>>n;
    p.EB(n);
    for(int i=2;i*i<=n;++i){
      if(n%i==0){
        p.EB(i);
        if(n!=i*i)p.EB(n/i);
      }
    }
    if(p.size()==1)cout<<n<<endl<<0;
    else if(p.size()==2)cout<<p[0]<<' '<<p[1]<<endl<<0;
    else if(p.size()==3){
      cout<<p[0]<<' '<<p[1]<<' '<<p[2]<<endl;
      if(gcd(p[1],p[2])==1)cout<<1;
      else cout<<0;
    }
    else{
      set<int>st;
      for(int i=2;i*i<=n;++i){
        if(n%i==0){
          pp.EB(i),st.IN(i);
          while(n%i==0)n/=i;
        }
      }
      if(n>1&&!st.CT(n))pp.EB(n);
      int l1=pp.size(),l2=p.size();
      if(l1==2){
        mp[pp[0]]=mp[pp[1]]=1;
        _for(i,0,l2)if(p[i]%(pp[0]*pp[1])==0)mp[p[i]]=1;
        cout<<pp[0]<<' ';
        _for(j,0,l2){
          if(!mp[p[j]]&&p[j]%pp[0]==0){
            cout<<p[j]<<' ';
            mp[p[j]]=1;
          }
        }
        cout<<pp[0]*pp[1]<<' '<<pp[1]<<' ';
        _for(j,0,l2){
          if(!mp[p[j]]&&p[j]%pp[1]==0){
            cout<<p[j]<<' ';
            mp[p[j]]=1;
          }
        }
        _for(j,0,l2)if(p[j]%pp[1]==0&&p[j]!=pp[0]*pp[1]&&p[j]%(pp[0]*pp[1])==0&&p[j]!=pp[1])cout<<p[j]<<' ';
      }
      else{
        _for(i,0,l1)mp[pp[i]]=1,mp[pp[i]*pp[(i+1)%l1]]=1;
        _for(i,0,l1){
          cout<<pp[i]<<' ';
          _for(j,0,l2){
            if(!mp[p[j]]&&p[j]%pp[i]==0){
              cout<<p[j]<<' ';
              mp[p[j]]=1;
            }
          }
          cout<<pp[i]*pp[(i+1)%l1]<<' ';
        }
      }
      cout<<"\n0";
    }
    cout<<endl;
  }
  return 0;
}

• 本文作者： baddog
• 本文链接： https://katoli.github.io/2020/09/24/Codeforces-Round-671-Div-2/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！