4396: C维护集合(set)
内存限制:512 MB
时间限制:2.000 S
评测方式:文本比较
命题人:
提交:8
解决:2
题目描述
### C维护集合(set)
小 A 最近学习了数论的相关知识,若 $a$ 是 $b$ 的约数,则 $b$ 能够被 $a$ 整除,即 $b\bmod a=0$ 。
学习之后,他发现自己很喜欢约数,便定义了 $c$ 重约数。若 $a$ 是 $b$ 的 $c$ 重约数,则 $b$ 能够被 $a^c$ 整除,即 $b\bmod a^c=0$ 。
之后小 A 思考了这样一个问题:小 A 需要维护一个初始大小为 $n$ 的集合 $a$ 。小 A 需要支持在集合 $a$ 上的 $Q$ 次操作,操作共三种,参数分别如下:
* `1 t`删除集合中的一个元素 $t$ ,保证该元素 $t$ 在集合中存在。
* `2 t`往集合中加入一个元素 $t$ 。
* `3 x`求出最大的 $k$ ,使得集合中存在一个数 $y$,是 $x$ 的 $k$ 重约数。(注:$k$ 是可以为 $0$ 的)
但小 A 并不会做,所以他来请你回答这个问题。
输入
第 $1$ 行包含两个正整数 $n,Q$,表示初始集合大小,操作次数。
第 $2$ 行包含 $n$ 个正整数 $a_1,a_2,...,a_n$ 表示初始集合。
随后 $n$ 行,每行描述一次操作,见题意。保证数据合法。
输出
包含 $q$ 行,其中 $q$ 是操作三的个数。
样例输入 复制
5 8
4 4 6 2 7
2 3
3 9
1 2
3 6
1 4
3 3
1 6
3 6
样例输出 复制
2
1
1
1
提示
### 样例一
#### 输入
```
5 8
4 4 6 2 7
2 3
3 9
1 2
3 6
1 4
3 3
1 6
3 6
```
#### 输出
```
2
1
1
1
```
对于所有数据 $n,q,a_i,x,t\le 10^5,a_i,t\neq1$ 。
| 测试点 | $n\le$ | $q\le$ | $x\le$ | $a_i,t\le $ | 特殊性质 |
| ----------- | ------ | ------ | ------ | ----------- | ---------- |
| $1\sim 4$ | $10$ | $10$ | $10$ | $10$ | 无 |
| $5\sim 10$ | $10^3$ | $10^3$ | $10^3$ | $10^3$ | 无 |
| $11\sim 12$ | 无限制 | $10^3$ | 无限制 | $10^3$ | 无 |
| $13\sim 14$ | 无限制 | 无限制 | $300$ | 无限制 | 无 |
| $15\sim 16$ | 无限制 | 无限制 | 无限制 | 无限制 | $\text{A}$ |
| $17\sim 20$ | 无限制 | 无限制 | 无限制 | 无限制 | 无 |
$\text{A}:$ 保证没有操作 $1,2$ 。