P1871 对撞机

    • 97通过
    • 485提交
  • 题目提供者 JosephZheng
  • 评测方式 云端评测
  • 标签 模拟 Special Judge 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    在2312年,宇宙中发现了n台巨型对撞机,这些对撞机分别用1-n的自然数标识。科学家们不知道启动这些对撞机会发生什么危险事故,所以这些机器,刚开始都是出于关闭的状态。

    随着科学家们的研究发现,第i台对撞机启动是安全的,如果其他已经启动的对撞机的标识数都跟着台对撞机标识数互质。(例如假设前面启动的是j,如果i能启动,那么i,j互质,也就是i,j的最大公约数为1)。如果两台对撞机不互为质数就启动,那么就会发生爆炸事故。

    基于前面的研究,科学家们准备做各种启动和关闭对撞机的实验。为了确保科学家们的生命安全,你要设计一个远程遥控的软件。

    刚开始,所有的额对撞机都是关闭状态。你的程序将会收到许多询问,格式为“启动、关闭第i台对撞机”。这个程序应该能处理这些询问(根据收到询问的先后顺序处理)。程序按照如下的格式输出处理结果。

    如果询问时“+i”(表示第i台对撞机启动),这程序应该按照下面三种的情况之一输出结果。

    (1)“Success”,表示启动第i台是安全的。

    (2)“Already on”,表示第i台在询问之前就已经启动了。

    (3)“Conflict with j”,如果第i台隔年面启动了的第j台冲突,就不能启动第i;如果前面有多台跟i冲突,那么只输出其中任何一台即可。

    如果寻味是“-i”(表示关闭第i台对撞机),这程序应该按照下面两种情况之一输出结果。

    (1)“Success”,表示关闭第i台对撞机

    (2)“Already off”,表示第i台对撞机在询问之前就已经关闭了。

    输入输出格式

    输入格式:

    第一行输入两个空格隔开的整数n和m(1<=n,m<=10^5),分别表示对撞机的数量和询问数。

    接下来m行,表示询问,每行要么为“+ i”,要么为“- i”(不含引号)(1<=i<=n)。

    输出格式:

    输出m行,输出结果按照上面题目给定格式输出。

    输入输出样例

    输入样例#1: 复制
    10 10 
    + 6
    + 10
    + 5
    - 10
    - 5
    - 6
    + 10 
    + 3
    + 6
    + 3
    
    输出样例#1: 复制
    Success
    Conflict with 6
    Success
    Already off
    Success
    Success
    Success
    Success
    Conflict with 3
    Already on
    

    说明

    感谢 @cn:苏卿念 提供Special Judge

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。