ARC 118 C - Coprime Set 解説

atcoder.jp

問題

以下の条件を満たす長さNの数列Aを構築せよ。

• 
• 
• 数列のどの2つの要素も互いに素ではない
• 

解説

まず、どの2つの要素も互いに素ではなく、一方で全体のgcd は1である、という点に着眼し、数列の要素を3つのグループに分けることを考える。

• グループ1：2*3の倍数でかつ5の倍数ではない
• グループ2：3*5の倍数でかつ2の倍数ではない
• グループ3：5*2の倍数でかつ3の倍数ではない

このように3つのグループを作ると、どのグループの要素も他のグループの要素と1以外の約数を持ち、かつ全体の gcd は1にできる。

それぞれのグループの要素の最大個数をカウントしてみると以下の様になる。

• グループ1：10000/6-10000/30=1666-333=1333
• グループ2：10000/15-10000/30=666-333=333
• グループ3：10000/10-10000/30=1000-333=667
• 合計：2333

合計が最大ケースに対して167個足りないとわかる。（初見時はここで詰まった。）

ここで構築した数列Aを観察してみると、グループ1～3の要素が1つずつ既に存在しているなら、2*3*5の倍数をAに追加しても問題ないことに気付く。（全体の gcd が1であることは保たれるし、2*3*5の倍数の要素は他のどの要素とも1以外の約数を持つ）

グループ4を2*3*5の倍数の要素とすれば、その最大個数は333個となるので、これで2500個の最大ケースにも対応することができた。

（素数7を増やすことでグループを増やしたくなるが、この場合は逆に作れる要素数が減少してしまう。）

実装

#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
template<class t> using vc=vector<t>;

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  
  int n; cin>>n;
  
  vc<int> a;
  a.push_back(6);
  a.push_back(15);
  a.push_back(10);
  
  int now=2, x=6;
  while(now*x<=10000){
    if(now%5==0){
      now++;
      continue;
    }
    a.push_back(now*x);
    now++;
  }
  now=2,x=15;
  while(now*x<=10000){
    if(now%2==0){
      now++;
      continue;
    }
    a.push_back(now*x);
    now++;
  }
  now=2, x=10;
  while(now*x<=10000){
    if(now%3==0){
      now++;
      continue;
    }
    a.push_back(now*x);
    now++;
  }
  
  // グループ4
  a.push_back(30);
  now=2, x=30;
  while(now*x<=10000){
    a.push_back(now*x);
    now++;
  }
  
  rep(i,n){
    cout<<a[i]<<endl;
  }
}