复杂度 $\sqrt{n}$ 的代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>

using namespace std;

const int N = 100010; // 17

int factors[N];
bool st[N];
int n, m;

bool have_factors(int x) // 判断x是否与前面的机器冲突（是否有被标记的因子） 
{
	for (int i = 2; i <= x / i; i ++ )
		if (x % i == 0)
		{
			if (factors[i]) return true;
			if (factors[x / i]) return true;
		}
		
	return false;
}

void make_factors(int x)
{
    factors[x] ++ ;
	for (int i = 2; i <= x / i; i ++ )
		if (x % i == 0)
		{
			factors[i] ++ ;
			if (i * i != x)
				factors[x / i] ++ ;
		}
}

int get_confliction(int x) // 找到与 x 冲突的值 
{
	for (int i = 2; i <= x / i; i ++ )
		if (x % i == 0)
		{
			if (factors[i])
				for (int j = i; j <= n; j += i)
					if (st[j])
						return j;
						
			int k = x / i;
			if (factors[k])
				for (int j = k; j <= n; j += k)
					if (st[j])
						return j;
		}
}

void cancel_factors(int x) // 将 x 的因数 - 1  
{
    factors[x] -- ;
	for (int i = 2; i <= x / i; i ++ )
		if (x % i == 0)
		{
			factors[i] -- ;
			if (i * i != x)
				factors[x / i] -- ;
		}
}

int main()
{
	scanf("%d%d", &n, &m);
	
	while (m -- )
	{
		char op[2];
		int x;
		scanf("%s%d", op, &x);
		
		if (x == 1)
		{
		    if (*op == '+')
		    {
    		    if (st[1]) puts("Already on");
    		    else puts("Success"), st[1] = true;
		    }
		    else
		    {
		        if (!st[1]) puts("Already off");
		        else puts("Success"), st[1] = false;
		    }
		}
		
		else
		{
		    if (*op == '+')
    		{
    			if (st[x]) puts("Already on");
    			else if (!have_factors(x)) puts("Success"), make_factors(x), st[x] = true; // 如果合法，输出并将 x 之前的所有质数标记上 
    			else printf("Conflict with %d\n", get_confliction(x)); // 否则，输出冲突 
    		}
    		else
    		{
    			if (!st[x]) puts("Already off");
    			else puts("Success"), cancel_factors(x), st[x] = false; // 将 x 之前的质因子取消 
    		}
		}
	}
	
	return 0;
}