### SpartanWarrior's blog

By SpartanWarrior, history, 2 years ago,  Comments (5)
 » HintUse a range query data structure such as segment tree/sparse table. SolutionThe solution that I found most common after having solved the problem was using a range query data structure to answer queries on range [L, R] efficiently. I used a RQ DS too and so I'll explain a solution that uses segment tree.For a fixed point L, find the left most right boundary R such that $gcd([L, ..., R])$ is 1. Once we have such a value R, we can now move the left boundary. For any index i in [L, R], the $gcd([i, ..., R])$ will either be 1 or something greater. When we encounter a left boundary that makes gcd to something not 1, we start searching for another right boundary keeping the left boundary fixed. Among all such [L, R] endpoints, the one with maximum length is your answer.The solution using RQ DS is, imo, the most intuitive. The complexity you achieve this way is $O(n.log(n))$. You can use either segment tree or sparse table or any other logarithmic query associative DS to achieve this complexity. Note that the complexity actually seems like it's $O(n.log^2(n))$ because of gcd being in there but finding the gcd of an entire array is magically $O(n)$ approximately and not $O(n.({some \space log \space factor}))$.There also is a solution that uses something called a gcdqueue which is similar in structure to this but I do not understand it and will not explain.