Solution:
First of all, "The product of every subarray is equal to its LCM" means "All these numbers are mutually prime". "All these numbers are mutually prime" means "In all these numbers, the prime factors of any two numbers are different".
The simplest solution:
Start from $l$, continually try to extend new number from the right side. When we are trying to extend $i_1$th number, we check if for every $j\in[l, i_1-1]$, so that $gcd(a_j,a_{i_1})=1$.
Then start from $i_1$, we try extending in same way until $r$. Every try is a new segment.
A little faster solution:
We can see, in the solution above, the time complexity of each query is $O(n^2)$. Now we have a $O(n)$ solution for each query.
We define a array $last$, $last[i]$ represent the last index of $i$th prime number appear. And define array $next$, $next[pos]$ represent the maximum position can be extended from $pos$ (not include $next[pos]$).
So when we do prime factorization on $a_x$, we can find the last index $pos$ which has the same prime factor through $last[i]$. Of course $gcd(a_x,a_{pos})\neq 1$. So, we have $next[pos]=min(next[pos], x)$.
So we start from $l$, every time, we jump to $next[l]$ until $r$. Every jump is a new segment.
AC solution:
Even though it's $O(n)$ for each query, but there are $n$ queries in total. So the total complexity is $O(n^2)$. We need change it to $O(n\cdot log(n))$.
Let's define $dp[i][j]$, which represent the position jump $2^i$ times from $j$. So: $$dp[i][j]=dp[i-1][dp[i-1][j]]$$
So we start from $l$, find the maximum $i$ which $dp[i][j]<r$ by binary search. Keep repeating until no such $i$ is found.
Code:
