题解 P1871 【对撞机】

星小雨 · 2019-01-04 11:21:04 · 题解

首先多谢 @小可爱三岁七 （是这样打吧。。）大佬的spj。。
闲着无聊给水题写个题解= =
所需知识：通过线性筛的预处理进行质因数分解。。
由于线性筛中合数都是由最小能整除它的质数筛出的，所以对于所有数记录一下能整除它的最小质数，每次不断除当前数的最小整除质数就能做到质因数分解了。。
然后就进入正题吧。
关于这道题，要判断当前这台对撞器已经开启或关闭——这个简单，只需要一个标记数组储存一下当前对撞器的开/关状态。
若要开启对撞器，还需判断当前对撞器是否与先前的对撞器是否互质——这个也好办，两个数互质即它们无相同质因数，我们只需要标记每个数的所有质因数一下即可。
这方面的具体实现就是：
然后每开启一台对撞器，就先检查所有质因数有没有被标记，若有则产生冲突，否则就标记其所有质因子。
关闭对撞器也大致一样，将所有质因子的标记清空即可。
时间效率为O(n \text{log} n)（设n,m同阶），代码也很好写，不失为一道线性筛的入门题，写了这道题能对线性筛能筛的东西有更好的理解。。
代码如下：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int p[10005],q[100005],k[10005];
bool b[100005];
int main(){
    int n,m,a,x,t=0;char s[3];scanf("%d%d",&n,&m);
    for(int i=2;i<=n;++i){
        if(!b[i]) p[++t]=i,q[i]=t;
        for(int j=1;j<=t && (a=p[j]*i)<=n;++j){
            b[a]=1,q[a]=j;
            if(!(i%p[j])) break;
        }
    }
    memset(b,0,sizeof b);
    while(m--){
        scanf(" %s%d",s,&a);x=a;
        if(s[0]==43){
            if(b[a]){puts("Already on");continue;}
            while(x>1){if(k[q[x]]) break;x/=p[q[x]];}
            if(x!=1){printf("Conflict with %d\n",k[q[x]]);continue;}
            b[x=a]=1;puts("Success");while(x>1){k[q[x]]=a;x/=p[q[x]];}
        }
        else {
            if(!b[a]){puts("Already off");continue;}
            b[a]=0;puts("Success");while(x>1){k[q[x]]=0;x/=p[q[x]];}
        }
    }
    return 0;
}