P8327 [COCI 2021/2022 #5] Radio
题目描述
克罗地亚有 $n$ 个初始状态下关闭的电台。当同时开启两个电台 $i,j$ 且 $i,j$ 不互质时，它们会互相干扰。
你需要写一个支持下列操作的程序：
1. `S x`：将电台的状态取反，即将原来开启的电台关闭，将原来关闭的开启。
2. `C l r`：检查在 $[l,r]$ 内是否存在互相干扰的现象。如果存在，输出 `DA`，否则输出 `NE`。
输入格式
第一行两个正整数 $n,q$，分别表示电台个数和操作次数。
接下来的 $q$ 行，具体输入格式见题目描述。
输出格式
对于每一次 C 操作，输出 `DA` 或者 `NE`。
说明/提示
**【样例 1 解释】**
|C 操作序号|开启电台|是否互相干扰|
| :----------: | :----------: | :----------: |
|$1$|$1,2,3$|否|
|$2$|$1,2,3,6$|是|
|$3$|$1,3,6$|是|
**【数据规模与约定】**
**本题采用捆绑测试。**
- Subtask 1（10 pts）：$1 \le n \le 100$，$1 \le q \le 200$。
- Subtask 2（30 pts）：对于所有的 C 操作，$l=1,r=n$。
- Subtask 3（70 pts）：无特殊限制。
对于 $100\%$ 的数据，$1 \le n \le 10^6$，$1 \le q \le 2 \times 10^5$，$1 \le x \le n$，$1 \le l \le r \le n$。
**【来源】[COCI 2021-2022#5](https://hsin.hr/coci/contest5_tasks.pdf) Task 4 Radio。**