[数据结构与算法]D - Coprime 2「质因数分解」「思维」

D - Coprime 2

题目描述：

给你一个数组A，问1-m中有多少个k满足如下的式子 $gcd(k,i)=1,1<=i<=n,1<=k<=m$,

思路：

直接分解所有的A，然后用set存下来所有的素数，再暴力更新掉m中的数就行

代码1:

（这是第一遍写的自以为很屌但是很蠢的代码，用的和上面不是很相同，但又差不多，二者的区别是，这份代码没有用set存所有的素因子，而是用了bitset操作存

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m;
int tr[MAX];
int x;
int tot;
bitset<100005>b;
bitset<10005>ans;
int id[MAX];
int prim[MAX];
void init(int n){
    for(int i = 2; i <= n; ++i){
        if(!b[i]){
            prim[++tot] = i;
            id[i] = tot;
        }
        for(int j = 1; j <= tot && prim[j] * i <= n; ++j){
            b[prim[j] * i] = 1;
            if(i % prim[j] == 0)break;
        }
    }
}

void divid(int p){
    bitset<10005>bb;
    for(int i = 2; i <= p / i; ++i){
        while (p % i == 0) {
            bb[id[i]] = 1;
            p /= i;
        }
    }
    if(p > 1 && p <= m)bb[id[p]] = 1;
    ans |= bb;
}

bool vis[MAX];

void work(){
    cin >> n >> m;
    init(m);
    for(int i = 1; i <= n; ++i){
        cin >> x;
        divid(x);
    }
    for(int i = 1; i <= 10000; ++i){
        if(ans[i]){
            for(int j = prim[i]; j <= m; j += prim[i]){
                vis[j] = 1;
            }
        }
    }
    int num = 0;
    for(int i = 1; i <= m; ++i){
        if(!vis[i])++num;
    }
    cout << num << endl;
    for(int i = 1; i <= m; ++i){
        if(!vis[i])cout << i << endl;
    }
}

int main(){
    io;
    work();
    return 0;
}

代码2:

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m;
int x;
set<int>se;
void divid(int p){
    for(int i = 2; i <= p / i; ++i){
        while (p % i == 0) {
            se.insert(i);
            p /= i;
        }
    }
    if(p > 1)se.insert(p);
    
}

bool vis[MAX];

void work(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        cin >> x;
        divid(x);
    }
    for(auto x : se){
        for(int i = x; i <= m; i += x)vis[i] = 1;
    }
    int num = 0;
    for(int i = 1; i <= m; ++i){
        if(!vis[i])++num;
    }
    cout << num << endl;
    for(int i = 1; i <= m; ++i){
        if(!vis[i])cout << i << endl;
    }
}

int main(){
    io;
    work();
    return 0;
}