# PROBLEM LINK:

# DIFFICULTY

EASY-MEDIUM

# PREREQUISITES

Elementary Number Theory, Integer Factorization

# PROBLEM

You are given a number N. Answer for 3 types of queries

- Given K, find the numbers that are divisors to both N and K
- Given K, find the numbers that are divisors to N and divisible by K
- Given K, find the numbers that are divisors of N and not divisible by K

# QUICK EXPLANATION

We can factorize N into primes and store it with us.

Now for each query, we simply iterate through prime factors of N and find the power of the prime factor that occurs in K to answer each type of query. We know that there are O(log N) factors of either N or K. Thus, our algorithm will run in O(Q*(log N + log K)) time, which is sufficiently fast within the time limits.

# EXPLANATION

We can factorize N by trial division in O(√N) time.

Let the factorization of N be P_{1}^{R1}P_{2}^{R2}…P_{m}^{Rm}, for m prime factors. m can be at most O(log N).

For each of the queries, given K, we need to find the largest power of each prime in the set P = { P_{1}, P_{2} …, P_{m}}, that occurs in K. This can be done by trial division of K by each of the primes. K will be divided at most O(log K) times.

We will obtain a set S = { S_{1}, S_{2} …, S_{m}}, the highest power of each prime in the set P.

This will execute in at most O(log N) + O(log K) time.

### Type 1 query

The result is the number of divisors of the number whose prime factorization over the set P is

T = { min(S_{1}, R_{1}), min(S_{2}, R_{2}) …, min(S_{m}, R_{m})}.

This is equal to

∏_{i=1 to m}(T_{i} + 1).

### Type 2 query

If, for any i = 1 to m: S_{i} > R_{i}, the answer is 0.

Otherwise the answer can be calculated by finding the number of divisors of the number whose prime factorization over the set P is

T = { R_{1} - S_{1}, R_{2} - S_{2} …, R_{m} - S_{m}}.

This is equal to

∏_{i=1 to m}(T_{i} + 1).

### Type 3 query

The answer for this query is equal to the number of divisors of N - (the answer for the equivalent Type 2 query).

Thus if the query is not of type 1, we always find the answer to type 2 query and find the appropriate answer based on whether the query was of Type 2 or Type 3.

See the setters / testers solutions for implementation details.

# SETTERS SOLUTION

Can be found here

# TESTERS SOLUTION

Can be found here