AtCoder ABC 215 D

題目連結：AtCoder Beginner Contest 215: D – Coprime 2

題目敘述 :

給定 n, m 下一行會有 n 個數字，輸出所有k in 1~m，k是與所有數字皆互質的數。

範例輸入 1 :

3 12
6 1 5

範例輸出 1 :

3
1
7
11

題解 :

用埃氏篩法在log(n)的時間內做質因數分解，接著將所有數字的質因數聯集存在bitset中，最後判斷1~m的所有數字的質因數之中有無存於bitset中。

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

using ll=long long;
const ll N=100010;
#define IO_SPEEDUP ios::sync_with_stdio(0);cin.tie(0);
#define IO_INIT cout<<fixed<<setprecision(6);

int n,m;
int pri[N];
bitset<N> bt;

void init(){
    pri[1]=0;
    for(int i=2;i<N;++i){
        if(pri[i]==0){
            pri[i]=i;
            for(ll k=(ll)i*i;k<N;k+=i)
                pri[k]=i;
        }
    }
}

void div(int n){
    while(pri[n]>0){
        bt[pri[n]]=true;
        n/=pri[n];
    }
}

bool check(int n){
    while(pri[n]>0){
        if(bt[pri[n]]){
            return false;
        }
        n/=pri[n];
    }
    return true;
}

int main(){
    IO_SPEEDUP; IO_INIT;

    cin>>n>>m;
    init();

    for(int i=0;i<n;++i){
        int a;
        cin>>a;
        div(a);
    }

    vector<int> ans;
    for(int i=1;i<=m;++i){
        if(check(i)){
            ans.emplace_back(i);
        }
    }

    cout<<ans.size()<<"\n";
    for(auto i:ans){
        cout<<i<<"\n";
    }
}