Codeforces Round #109 (Div. 1) B : Colliders

問題概要

1~10^5の数字が書かれたフラグがある。最初は全てオフになっている。以下のQ(<10^5)個のクエリに答える問題。

1. iをオンにする。ただし、既にオンになっていたり、他のオンになっている数字と互いに素でなければ素の旨指摘してオンにしない。
2. iをオフにする。ただし、既にオフになっているときは指摘する。

解法

前処理として各数字に対して素因数を列挙しておく。これはエラトステネスっぽくやればよい。後は、番号iをオンやオフにするとき全ての約数の状態を見れば良い。

acceptされたコード

#include <cstdio>
#include <vector>
using namespace std;

const int MAX_N = (int)(1e5);

int N, M;
bool on[MAX_N + 1];
int ps[MAX_N + 1];

vector<int> primes[MAX_N + 1];

void init(){
	scanf("%d %d ", &N, &M);

	for(int i=2; i<=N; i++)if(primes[i].empty()){
		for(int j=i; j<=N; j+=i){
			primes[j].push_back(i);
		}
	}
}

void query(){
	char cmd;
	int x;
	scanf(" %c %d ", &cmd, &x);

	if(cmd == '+'){
		if(on[x]){
			puts("Already on");
		}
		else{
			int conflict = -1;
			for(int i=0; i<(int)primes[x].size(); i++)if(ps[primes[x][i]]){
				conflict = ps[primes[x][i]];
			}
			if(conflict == -1){
				on[x] = true;
				for(int i=0; i<(int)primes[x].size(); i++){
					ps[primes[x][i]] = x;
				}
				puts("Success");
			}
			else{
				printf("Conflict with %d\n", conflict);
			}
		}
	}
	else{
		if(!on[x]){
			puts("Already off");
		}
		else{
			for(int i=0; i<(int)primes[x].size(); i++){
				ps[primes[x][i]] = 0;
			}
			on[x] = false;
			puts("Success");
		}
	}
}

int main(){
	init();
	for(int i=0; i<M; i++){
		query();
	}

	return 0;
}