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: