Codeforces Round #109 (Div. 1)B 數論

Codeforces Round #109 (Div. 1)B 數論

//兩個數如果不是互質，那麼它們一定有一個質數因子
//用vec存入2到n的所有的質數因子
//用vis存入有該因子的數是否讀入
//處理時只需要維護vis這個數組就行
#include
#include
#include
#include
using namespace std ;
const int maxn = 100010 ;
vector vec[maxn];
int isp[maxn] ;
int vis[maxn] ;
int num[maxn] ;
void set()
{
memset(isp, 0 ,sizeof(isp)) ;
isp[1] = 1;
for(int i = 2;i < maxn ;i += 2)
{
isp[i] = 1;
vec[i].push_back(2) ;
}
for(int i = 3;i < maxn ;i++)
{
if(isp[i])continue ;
for(int j = i;j < maxn ;j+=i)
{
isp[j] = 1;
vec[j].push_back(i) ;
}
}
}
int main()
{
//freopen("input.txt" ,"r",stdin) ;
set() ;
int n , m ;
char ch;int i ;
while(~scanf("%d%d" ,&n , &m))
{
memset(num , 0 , sizeof(num)) ;
memset(vis , 0 , sizeof(vis)) ;
while(m--)
{
scanf("%c%c%d" ,&ch ,&ch, &i) ;
//cout< if(ch == '-')
{
//cout< if(!num[i])puts("Already off");
else
{
puts("Success");
num[i] = 0;
for(int j = 0;j < vec[i].size() ;j++)
vis[vec[i][j]] = 0;
}
}
if(ch == '+')
{
if(num[i])puts("Already on");
else
{
int flag = 0 ;
for(int j = 0;j < vec[i].size();j++)
{
int t = vec[i][j] ;
if(vis[t])
{
printf("Conflict with %d\n" , vis[t]) ;
flag = 1;
break;
}
}
if(!flag)
{
puts("Success");
// cout< num[i] = 1;
for(int j = 0;j < vec[i].size();j++)
vis[vec[i][j]] = i;
}
}
}
}
}
return 0 ;
}