Official

D - Coprime 2 Editorial by physics0523


\(\gcd(a,b) \neq 1\) であるとは、 \(a\)\(b\) とが何らかの共通の素因数を持っているということです。
このことから、エラトステネスの篩の要領の、以下の解法が成立します。

  • 集合 \(S\)\(1\) から \(M\) まで全ての整数を入れる。
  • \(i\)\(1\) から \(N\) まで、以下を繰り返す。
    • \(A_i\) を素因数分解する。素因数の集合を \(P\) とする。
    • \(P\) に含まれる全ての素因数 \(k\) について、「 \(S\) から \(k\) の倍数をすべて削除する」という操作を行う。
    • なお、全体を通して同じ素因数に関して \(2\) 度以上操作を行う必要がないことを利用して、計算量を改善できる。(この部分を行わないとTLEします)
  • 操作終了後に \(S\) に残った整数が、解である。

とる方針により計算量は変化しますが、素因数分解を \(O(\sqrt{\max A})\) で行うことにより、遅くとも時間計算量 \(O(N \sqrt{\max A})\) の解法が達成されます。

実装例(C++)

#include<bits/stdc++.h>
#define SIZE 100005

using namespace std;

vector<int> pfact(int x){
  vector<int> res;
  for(int i=2;i*i<=x;i++){
    while(x%i==0){
      x/=i;
      res.push_back(i);
    }
  }
  if(x!=1){res.push_back(x);}
  return res;
}

int main(){
  int n,m;
  cin >> n >> m;
  vector<bool> fl(SIZE,true);
  for(int i=0;i<n;i++){
    int a;
    cin >> a;
    vector<int> v=pfact(a);
    for(auto &nx : v){
      if(fl[nx]){
        for(int j=nx;j<SIZE;j+=nx){fl[j]=false;}
      }
    }
  }
  vector<int> res;
  for(int i=1;i<=m;i++){
    if(fl[i]){res.push_back(i);}
  }
  cout << res.size() << '\n';
  for(auto &nx : res){cout << nx << '\n';}
  return 0;
}

posted:
last update: