If we replace each element of the array with all its divisors, then query for the maximum GCD is query on maximum element of subarray, that meets twice. For solve this problem we can use a technique similar to DQUERY.

We will solve this problem offline. First, create event of two type:

• $$$1 \ l \ r \ d \ -$$$ divisor $$$d$$$ divide $$$a_r$$$ and $$$a_l$$$, $$$l < r$$$ and $$$l$$$ is the maximum possible for fixed $$$r$$$
• $$$2 \ l \ r \ i \ -$$$ $$$i$$$-th query

For generate query of first type we need factorize every elements of array $$$a$$$ and for every divisor $$$d$$$ remember index of element, that divide into $$$d$$$. This can be done with std::map.

Sort event first by $$$r$$$, than by type.

Iterate on event and if handle first type we need to do $$$C_l = max(C_l, d)$$$, if handle second type event we need to find $$$max(C_l, C_{l+1},...,C_r)$$$ — it's answer for $$$i$$$-th query. This can be done with data structure segment tree or BIT.

Calculate complexity. We factorize all elements of array $$$O(n \sqrt A)$$$, each divisor we update in map $$$O(n \sqrt[3] A \cdot log(n \sqrt[3] A)) $$$ and use segment tree for answer on query $$$O((q + n \sqrt[3] A)\cdot log(n))$$$.

Total complexity this solution is $$$O(n \sqrt A + n \sqrt[3] A \cdot log(n \sqrt[3] A) + q \cdot log(n))$$$. My solution work in 0.6 seconds.

You can read editorial here https://discussed.codechef.com/questions/125148/gqr-editorial