A16199. Vasilije Loves Number Theory
编程题
普及/提高-
知识点
题目描述
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.
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$ .
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).
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".
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".