Range GCD Queries

Difficulty: 1700 4000 ms 128 MB

math sparse-table

Each query gives L and R and asks for gcd(a_L, ..., a_R).

Input: the first line has N and Q; the second line has N positive integers; each of the next Q lines has L and R.

Output: Q lines — the range gcd per query.

Constraints:

• 1 ≤ N, Q ≤ 10⁵
• 1 ≤ a_i ≤ 10⁹

Sample Tests

5 2
12 18 24 8 16
1 3
3 5

6
8

1 1
7
1 1

7

Read the Editorial