预处理...由于10^5<2^20..所以每个数的质因子个数最多20个..为了避免重复运算..将素有数的质因子打表出来...
两个数如果互质..那么他们的最大公约数为1..反过来说..两个数如果不互质..那么他们的必定有相同的质因子...
问题就简单了....由于要保证不冲突..所以每个质因子至多对应一个数...用w[i]记录一个数对应的数..w[i]==0说明其没用对应的数...
那么如果要+k..则先判断其质因子上是否已经有其他的数了..如果没有..将其质因子w[i]=k (i为k的所有质因子)..删除一个数..将其所有的质因子w[i]=0...
练习赛的时候2B了..把约数表打错了！！搞得一直过不了....
Pragram:
#include<iostream>
#include<stack>
#include<queue>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<cmath>
#define ll long long
#define oo 1000000007
#define MAXN 100005
using namespace std;
int used[MAXN],Prime[MAXN],w[MAXN],N[MAXN],T[MAXN][30];
char c;
bool A[MAXN],P[MAXN];
bool IsPrime(int x)
{
for (int i=2;i*i<=x;i++)
if (x%i==0) return false;
return true;
}
void PreWork()
{
int i,num,x,k;
num=0;
memset(P,false,sizeof(P));
for (i=2;i<=100000;i++)
if (IsPrime(i)) Prime[++num]=i,P[i]=true;
memset(N,0,sizeof(N));
for (i=2;i<=100000;i++)
{
k=i;
for (x=1;Prime[x]*Prime[x]<=k;x++)
if (k%Prime[x]==0)
{
T[i][++N[i]]=Prime[x];
while (k%Prime[x]==0) k/=Prime[x];
}
if (P[k]) T[i][++N[i]]=k;
}
}
int main()
{
int x,y,n,m,i;
PreWork();
while (~scanf("%d%d",&n,&m))
{
memset(A,false,sizeof(A));
memset(w,0,sizeof(w));
while (m--)
{
c=getchar();
while (c!='+' && c!='-') c=getchar();
scanf("%d",&x);
if (c=='+')
{
if (A[x]) printf("Already on
");
else
{
for (i=1;i<=N[x];i++)
if (w[T[x][i]]) break;
if (i<=N[x]) printf("Conflict with %d
",w[T[x][i]]);
else
{
printf("Success
"),A[x]=true;
for (i=1;i<=N[x];i++) w[T[x][i]]=x;
}
}
}else
{
if (!A[x]) printf("Already off
");
else
{
printf("Success
");
for (i=1;i<=N[x];i++) w[T[x][i]]=0;
}
A[x]=false;
}
}
}
return 0;
}