CF1878F Vasilije Loves Number Theory

Vasilije 是一名聪明的学生，他的离散数学老师 Sonja 非常好地教会了他数论。 他给了 Ognjen 一个正整数 $n$。 记 $d(n)$ 为 $n$ 的正整数约数的个数，记 $gcd(a, b)$ 为最大的整数 $g$，使得 $a$ 和 $b$ 都能被 $g$ 整除。 之后，他给了 Ognjen $q$ 个询问，这些询问有两种类型。 - $1$，$x$ —— 将 $n$ 变为 $n \cdot x$，然后回答以下问题：是否存在正整数 $a$，使得 $gcd(a, n) = 1$，且 $d(n \cdot a) = n$？ - $2$ —— 将 $n$ 重置为初始值（即所有操作之前的值）。 注意，经过类型 $1$ 的询问后，$n$ 不会恢复到初始值。 由于 Ognjen 害怕数论，Vasilije 向他保证，每次询问后都有 $d(n) \le 10^9$，但即使有这个限制，他仍然需要你的帮助来解决这个问题。

第一行包含一个正整数 $t$，$(1 \le t \le 100)$ —— 表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $q$，$(1 \le n \le 10^{6},\ 1 \le q \le 1000)$ —— 初始的 $n$ 和询问的数量。 接下来的 $q$ 行，每行包含一个整数 $k$，$(1 \le k \le 2)$，如果 $k=1$，则该行还包含一个整数 $x$，$(1 \le x \le 10^6)$ —— 表示该询问的描述。 保证对于给定的输入，任意时刻 $d(n)$ 都不会超过 $10^9$。 保证所有测试用例中 $q$ 的总和不超过 $10^3$。

对于每个类型 $1$ 的询问，如果存在正整数 $a$，使得 $gcd(a, n) = 1$ 且 $d(n \cdot a) = n$，输出 "YES"；否则输出 "NO"。 你可以用任意大小写输出答案（例如 "yEs"、"yes"、"Yes"、"YES" 都会被认为是正确答案）。

在第一个测试用例中，初始 $n=1$。 第一次询问后：$n=1$，$d(n)=1$，取 $a=1$，$d(n \cdot a)=n$，答案为 "YES"。 第二次询问后：$n=2$，$d(n)=2$，同样取 $a=1$，$d(n \cdot a)=n$，答案为 "YES"。 第三次询问：$n=1$，这是类型 $2$ 的询问，不需要输出答案。 第四次询问后：$n=8$，取 $a=3$，$d(n \cdot a)=d(24)=8=n$，答案为 "YES"。 第五次询问后：$n=72$，可以取 $a=637$，使得 $n \cdot a=45864$，$d(n \cdot a)=72=n$，答案为 "YES"。 在第二个测试用例中，初始 $n=20$。 第一次询问后：$n=60$，答案为 "YES"。 第二次询问：$n=20$，类型 $2$ 的询问，不需要输出答案。 第三次询问后：$n=140$，可以证明无论取哪个正整数 $a$，$d(n \cdot a)$ 都不会等于 $n$，答案为 "NO"。 第四次询问后：$n=1680$，可以证明存在正整数 $a$，使得 $d(n \cdot a)=n$，答案为 "YES"。 由 ChatGPT 4.1 翻译