← 返回题目列表

Codeforces · 1878/F

F. Vasilije 热爱数论

中文机器翻译题面 查看原题

Vasilije 是一个聪明的学生,他的离散数学老师 Sonja 把他的数论教得很好。

他给了 Ognjen 一个正整数 $$$n$$$。

将 $$$d(n)$$$ 表示为 $$$n$$$ 的正整数除数的数量,并将 $$$gcd(a, b)$$$ 表示为最大整数 $$$g$$$,使得 $$$a$$$ 可被 $$$g$$$ 整除,$$$b$$$ 可被 $$$g$$$ 整除。

之后,他给了 Ognjen $$$q$$$ 查询,并且有 $$$2$$$ 类型的查询。

- $$$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$$$) — 测试用例的数量。

每个测试用例的第一行包含 $$$2$$$ 整数、$$$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”将被识别为肯定答案)。

示例

输入 #1

7
1 5
1 1
1 2
2
1 8
1 9
20 4
1 3
2
1 7
1 12
16 10
1 6
1 6
1 10
1 9
1 1
1 9
1 7
1 3
1 2
1 10
9 1
1 3
8 1
1 2
8 3
1 5
1 8
1 10
11 5
1 8
1 2
1 1
1 3
1 1

输出 #1

YES
YES
YES
YES

YES
NO
YES

YES
NO
YES
YES
YES
NO
YES
NO
YES
YES

NO

NO

YES
NO
NO

YES
NO
NO
NO
NO

注意

在第一个测试用例中,我们最初有 $$$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”。