P1871 对撞机

通过线性筛标记所有分解质因数

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int n,m;
bool running[MAXN];          // 是否运行
int prime_owner[MAXN];       // 占用情况
int isp[MAXN];               // 筛标
vector<int> primes;          
void init(){
    for(int i=2;i<=n;i++){
        if(isp[i]==0){
            isp[i]=i;
            primes.push_back(i);
        }
        for(int p:primes){
            if(p*i>n) break;
            isp[p*i]=p;
            if(i%p==0) break;
        }
    }
}
vector<int> factorize(int x) {
    vector<int> res;
    while(x>1){
        int p=isp[x];
        res.push_back(p);
        while(x%p==0) x/=p;
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    init();
    while(m--){
        char op;
        int x;
        cin>>op>>x;
        if(op=='+'){
            if(running[x]){
                cout<<"Already on\n";
                continue;
            }
            vector<int> factors=factorize(x);
            int t=-1;
            for(int p:factors)
                if(prime_owner[p]!=0){
                    t=prime_owner[p];
                    break;
                }
            if(t!=-1) cout<<"Conflict with "<<t<<"\n";
            else {
                running[x]=true;
                for(int p:factors) prime_owner[p]=x;
                cout<<"Success\n";
            }
        } 
        else {
            if(!running[x]) cout<<"Already off\n";
            else {
                running[x]=false;
                vector<int> factors=factorize(x);
                for(int p:factors)
                    if(prime_owner[p]==x) prime_owner[p]=0;
                cout<<"Success\n";
            }
        }
    }
    return 0;
}