Vasilije Loves Number Theory

题意翻译

令 $d(x)$ 表示 $x$ 的正因子数量,给定 $n,q$。现有两种操作: 1. 给定 $x$,令 $n\gets n\cdot x$。同时询问是否存在一个正整数 $a$ 满足 $\gcd(a,n)=1$ 且 $d(n\cdot a)=n$。 2. 将 $n$ 还原为最初的值。 数据保证任何时刻,$d(n)\leq 10^9$。 translated by @[StayAlone](https://www.luogu.com.cn/user/409236)

题目描述

Vasilije is a smart student and his discrete mathematics teacher Sonja taught him number theory very well. He gave Ognjen a positive integer $ n $ . Denote $ d(n) $ as the number of positive integer divisors of $ n $ , and denote $ gcd(a, b) $ as the largest integer $ g $ such that $ a $ is divisible by $ g $ and $ b $ is divisible by $ g $ . After that, he gave Ognjen $ q $ queries, and there are $ 2 $ types of queries. - $ 1 $ , $ x $ — set $ n $ to $ n \cdot x $ , and then answer the following question: does there exist a positive integer $ a $ such that $ gcd(a, n) = 1 $ , and $ d(n \cdot a) = n $ ? - $ 2 $ — reset $ n $ to its initial value (before any queries). Note that $ n $ does not get back to its initial value after the type 1 query. Since Ognjen is afraid of number theory, Vasilije promised him that after each query, $ d(n) \le 10^9 $ , however, even with that constraint, he still needs your help with this problem.

输入输出格式

输入格式


The first line contains a positive integer $ t $ , ( $ 1 \le t \le 100 $ ) — the number of test cases. The first line of each test case contains $ 2 $ integers, $ n $ and $ q $ ( $ 1 \le n \le 10^{6} $ , $ 1\le q \le 1000 $ ) — the number $ n $ and the number of queries. The following $ q $ lines contain an integer $ k $ ( $ 1 \le k \le 2 $ ), if $ k=1 $ then there is another integer in this line $ x $ ( $ 1 \le x \le 10^6 $ ) — the description of the queries. It is guaranteed that, for the given input, $ d(n) $ does not exceed $ 10^9 $ at any point. It is guaranteed that the sum of $ q $ over all test cases doesn't exceed $ 10^3 $ .

输出格式


For each type 1 query, you should output "YES" if there exist such positive integer $ a $ that $ gcd(a, n) = 1 $ and $ d(n \cdot a)=n $ , and "NO" if he can't. You can output the answer in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as a positive answer).

输入输出样例

输入样例 #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

说明

In the first test case, we initially have $ n=1 $ . After the first query: $ n=1 $ , $ d(n)=1 $ , so by taking $ a = 1 $ , $ d(n \cdot a) = n $ , and the answer to this query is "YES". After the second query: $ n=2 $ , $ d(n)=2 $ , we can, again, take $ a = 1 $ , $ d(n \cdot a) = n $ , and the answer to this query is "YES". After the third query $ n=1 $ , and this is a type $ 2 $ query so we don't answer it. After the fourth query: $ n=8 $ , and by taking $ a=3 $ , $ d(n \cdot a) = d(24) = 8 = n $ , so the answer is "YES". After the fifth query: $ n=72 $ , now we can take $ a=637 $ to get $ n \cdot a = 45864 $ , and $ d(n \cdot a) = 72 = n $ , so the answer is "YES". In the second test case, we initially have $ n=20 $ . After the first query: $ n=60 $ , and the answer is "YES". After the second query: $ n=20 $ , this is a type $ 2 $ query, so we don't answer it. After the third query: $ n=140 $ , and it can be proven that no matter which positive integer $ a $ we take, $ d(n \cdot a) $ will never be equal to $ n $ , so the answer to this query is "NO". After the fourth query: $ n=1680 $ . It can be proven that there exists a positive integer $ a $ , such that $ d(n \cdot a) = n $ , so the answer is "YES".