牛客-game with numbers(筛法)

game with numbers

给定大小为 $n$ 的集合 $S$
一个数被称作合法的，当且仅当 $x \in S$ 或者 $x$ 存在大于1的真因数，且这些真因数均是合法的
求有多少个数 $x$ 满足 $2 \leq x \leq m$ 且 $x$ 合法
PS: $x$ 的真因数指不是 $x$ 本身的约数

T组数据
每组数据给定 $n 和 m$
接下来一行 $n$ 个数字，表示集合 $S$

思路：先将范围内所有数的真因数个数统计出来。若某个数是质数，就将它的因数个数定位INF，便于与题意符合。然后利用给定的 $n$ 个数进行因数的筛除，若某个数的因数被完全筛除，则表明这个数满足条件。

//#pragma comment(linker, "/STACK:102400000,102400000") 
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {
    int x=0;
    char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0', c=getchar();
    return x;
}

const int maxn = 3e5+10;
const int mod = 1e9+7;
const double eps = 1e-9;

int n, m;
int cnt[maxn];

void solve() {
    memset(cnt,0,sizeof(cnt));
    for(int i=2; i<maxn/2; ++i) {
        for(int j=2*i; j<maxn; j+=i) cnt[j]++;  //统计因数个数
    }
    for(int i=2; i<maxn; ++i) if(cnt[i]==0) cnt[i]=1e9; //质数的特殊处理
    n=read(), m=read();
    for(int i=0; i<n; ++i) cnt[read()]=0; //这些数为合法数
    int ans=0;
    for(int i=2; i<=m; ++i) {
        if(cnt[i]<=0) { //表明这个数是合法的
            ans++; 
            for(int j=2*i; j<=m; j+=i) cnt[j]--; //利用合法数进行后续的数的因数的筛除
        }
    }
    cout<<ans<<endl;
}

int main() {
    //ios::sync_with_stdio(false);
    int T=read();
    while(T--) solve();
}