Vasilije Loves Number Theory
Contest: Codeforces Round 900 (Div. 3)
Difficulty rating: 1900
Tags: brute force, math, 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.

Input format:
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$$$.

Output format:
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).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
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

Example output:
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

Editorial:
Answer: a solution exists if and only if $$$d(n)$$$ divides $$$n$$$.
Proof: consider the prime factorization of the number $$$n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdots p_k^{\alpha_k}$$$, where $$$p_i$$$ represents the $$$i$$$-th prime number, and $$$\alpha_i$$$ represents the highest power of the $$$i$$$-th prime number such that $$$p_i^{\alpha_i}$$$ divides $$$n$$$. Knowing this we can calculate the number of divisors of $$$n$$$ with the following formula: $$$d(n) = (\alpha_1+1) \cdot (\alpha_2+1) \cdots (\alpha_k+1)$$$.
Let's now consider the operations we are performing. We are multiplying the number $$$n$$$ by a number $$$a$$$ that has no common prime factors with $$$n$$$ (condition $$$gcd(a, n) = 1$$$).
Multiplying $$$n$$$ by any integer will only bring new prime factors to $$$n$$$, which means that we can not change what is already in the brackets of the formula for the number of divisors $$$d(n)$$$, but we can add new brackets. Therefore, $$$d(n)$$$ will always be a divisor of the number $$$d(n\cdot a)$$$. So, we can write $$$d(n \cdot a) = v \cdot d(n)$$$. In order to achieve $$$d(n \cdot a) = n$$$, we must also have $$$v \cdot d(n) = n$$$. Therefore, it is necessary for $$$d(n)$$$ to be a divisor of $$$n$$$. Let's show that this is also sufficient. Let's denote $$$k = \frac{n}{d(n)}$$$. Choose any prime number $$$p$$$ that is not a factor of $$$n$$$ (such a prime exists because there are infinitely many prime numbers, while $$$n$$$ has a finite number of prime factors). By multiplying $$$n$$$ by $$$a = p^{k-1}$$$, we obtain $$$d(n\cdot a) = d(n) \cdot k = n$$$.
Using this fact, we just need to efficiently check whether $$$d(n)$$$ divides $$$n$$$ after each type 1 query. How do we do this?
First we pre-calculate for each positive integer less than $$$10^6$$$ its smallest prime factor. This allows us to factorize all numbers smaller than or equal to $$$10^6$$$ in logarithmic time. We also factorize $$$n$$$ and find its number of divisors using the formula mentioned above, and store for each prime factor its highest power which still divides $$$n$$$. We can do this using an array, or using a map, either way, let's call this structure $$$power$$$.
Now we need to deal with the queries:
For type 2 query we just need to reset everything.
For the first query, we factorize $$$x$$$ in $$$\mathcal{O}(\log{x})$$$ operations and let $$$x = r_1^{\beta_1} \cdot r_2^{\beta_2} \cdots r_\ell^{\beta_\ell}$$$ be the factorization of the number $$$x$$$. We update the $$$d(n)$$$ by doing the following: for each prime $$$r_i$$$ in $$$x$$$, divide $$$d(n)$$$ by $$$power[r_i]+1$$$, then add $$$\beta_i$$$ to $$$power[r_i]$$$, and then multiply $$$d(n)$$$ by $$$power[r_i]+1$$$. After we calculate $$$d(n)$$$, we should check if $$$n$$$ is divisible by it. We can do this in 2 ways:
Solution 1:
We do this by multiplying the value of all previous type $$$1$$$ queries (after the last type $$$2$$$ query), and the value of the starting $$$n$$$ by modulo $$$d(n)$$$, because $$$n$$$ can get really large, and we can't store it in a 64-bit integer. If the value mod $$$d(n)$$$ is $$$0$$$, then its divisible and the answer to our query is "YES", else it is "NO".
Time complexity $$$\mathcal{O}(Q \cdot (Q + \log{x}) + \log{n})$$$.
Solution 2:
This solution is even faster, but it might be harder to implement, and that's why we didn't make it necessary.
Instead of storing queries, we just need to use another map to store the prime divisors of $$$d(n)$$$, now we can compare each prime divisor and its power for $$$d(n)$$$ and for the product of $$$n$$$ and all queries after the last reset. Now for each prime in $$$d(n)$$$, the power of that prime has to be smaller or equal to than the power of that prime in the product of $$$n$$$ and queries. Since $$$d(n) \le 10^9$$$, the map for $$$d(n)$$$ will have at most $$$\log(max(d(n))$$$ entries, so this solution runs in $$$\mathcal{O}(Q \cdot (\log(max(d(n)) \cdot log(log(max(d(n))) + \log(x))+ t \cdot \log(n))$$$.