Segment Tree, Factorize
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.
Every number X can be written in the factorized form: X = p1^k1 * p2^k2 * … * pi^ki * … * pn^kn. We can call all pi as X’s factors (of course, pis are all different primes). For example, 18 = 2 * 3^2. So we can say that 18, has factors 2 and 3. Because pi >= 2, the number of factors, i.e. 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[pi], which records the positions of the numbers who has the factor pi. From the analysis above, we know that the sum of position[pi].size() is O(NlogN)
- Build several segment trees, the i-th one corresponds to the position[pi], maintaining the interval maximum in the tree node. Of course, you can also concate all position and make a whole segment tree.
- 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.