### PROBLEM LINK:

**Author:** Anudeep Nekkanti

**Tester:** Mahbubul Hasan

**Editorialist:** Jingbo Shang

### DIFFICULTY:

Medium

### PREREQUISITES:

Segment Tree, Factorize

### PROBLEM:

Given **N** numbers in a sequence, answer **M** queries about what is the maximum number between **L** and **R** and the greatest common divisor between it and **G** is greater than 1.

### EXPLANATION:

Every number **X** can be written in the factorized form: **X = p _{1}^k_{1} * p_{2}^k_{2} * … * p_{i}^k_{i} * … * p_{n}^k_{n}**. We can call all

**p**as

_{i}**X**’s factors (of course,

**p**s are all different primes). For example, 18 = 2 * 3^2. So we can say that 18, has factors 2 and 3. Because

_{i}**p**>= 2, the number of factors, i.e.

_{i}**n**, is in

**O(logX)**. Therefore, the total number of factors of the given

**N**numbers are

**O(NlogN)**(the range of

**N**and numbers are same).

The greatest common divisor of two numbers is greater than 1, means that they have at least one common factor. If we enumerate the common factor **C** they have, the satisfied numbers are determined – all numbers have factor **C**. After that, the only thing we need is to find the maximum in the query interval **[L, R]**. For this type of queries, an ordinary solution is to use Segment Tree.

With these two ideas in mind, let’s start to assemble the whole algorithm, now.

- Factorize
**N**numbers, and restore some vectors of**position[p**, which records the positions of the numbers who has the factor_{i}]**p**. From the analysis above, we know that the sum of_{i}**position[p**is_{i}].size()**O(NlogN)** - Build several segment trees, the
**i**-th one corresponds to the**position[p**, maintaining the interval maximum in the tree node. Of course, you can also concate all position and make a whole segment tree._{i}] - For a query number
**X**and the interval**[L,R]**, first factorize**X**. And for each factor, look up in the corresponding segment tree (or corresponding intervals, if you choose to build a whole segment tree) to get the maximum. Finally, take the maximum of the query results among different factors.

As analyzed before ,**X** has at most **O(logX)** factors. And each interval-maximum query takes only **O(logN)** time. Therefore, to answer a query, our algorithm only needs **O(log^2 N)** time.

In summary, the time complexity is **O(NlogN + Qlog^2N)**, while **O(NlogN)** space needed.

As requested by many users here are solutions without segment trees.

Sqrt-Decomposition.

Binary Indexed Tree.

STL-MAP

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.