Codeforces 109 D - Colliders

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define forn(i,n) for(int i=0;i<(int)(n);i++)
#define forsn(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define forall(i,c) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
const int MAXN=100100;

int stat[MAXN],primes[MAXN], pc;
bool criba[MAXN];
int assig[MAXN];

void getprimes(int n){
    forn(i,n+1) criba[i]=true;
    for(int i = 2; i <= n; i++){
        if(criba[i]){
            for(int j = 2*i; j <= n; j+=i){
                criba[j]=false;
            }
        }
    }

    pc=0;
    for(int i=2;i<=n; i++){
        if(criba[i]){
            assig[i]=-1;
            primes[pc++]=i;
        }
    }
}

void remove(int n){
    forn(i,pc){
        if(primes[i]*primes[i] > n) break;

        bool div=false;
        while(n % primes[i] == 0){
            div=true;
            n /= primes[i];
        }
        if(div){
            assig[primes[i]]=-1;
        }
    }
    if(n > 1){
        assig[n]=-1;
    }
}

void add(int n){
    int k = n;
    forn(i,pc){
        if(primes[i]*primes[i] > n) break;

        bool div=false;
        while(n % primes[i] == 0){
            div=true;
            n /= primes[i];
        }
        if(div){
            assig[primes[i]]=k;
        }
    }
    if(n > 1){
        assig[n]=k;
    }
}

int check(int n){
    forn(i,pc){
        if(primes[i]*primes[i] > n) break;

        bool div=false;
        while(n % primes[i] == 0){
            div=true;
            n /= primes[i];
        }
        if(div){
            if(assig[primes[i]] > 0)
                return assig[primes[i]];
        }
    }
    if(n > 1){
        return assig[n];
    }
    return -1;
}

void solve(){
    int n,m; scanf("%d %d\n",&n,&m);
    getprimes(n+1);

    forn(i,n+1) stat[i] = 0;

    char c; int k;
    forn(i,m){
        scanf("%c %d\n",&c,&k); int j;

        if(c == '+'){
            if(stat[k]){
                printf("Already on\n");
            }else if((j = check(k)) != -1){
                printf("Conflict with %d\n",j);
            }else{
                printf("Success\n");
                add(k);
                stat[k]=1;
            }
        }else{
            if(!stat[k]){
                printf("Already off\n");
            }else{
                printf("Success\n");
                stat[k]=0;
                remove(k);
            }
        }
    }
}

int main(){
    #ifdef JUAMPI
        freopen("Colliders.in","r",stdin);
        int tests; cin >> tests;
        while(tests--) solve();
    #else
        solve();
    #endif
    return 0;
}