CF1878F 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.

N/A

N/A

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".