ANUGCD - Editorial



Author: Anudeep Nekkanti
Tester: Mahbubul Hasan
Editorialist: Jingbo Shang




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.

  1. 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)
  2. 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.
  3. 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.

As requested by many users here are solutions without segment trees.
Binary Indexed Tree.


Author’s solution can be found here.
Tester’s solution can be found here.


Is there an alternate solution that does not involve the usage of segment tree ?

1 Like

One possible way is sqrt decomposition, but I think it may get TLE. Let me further think about it.

I tried sqrt decomposition [ ], it got TLE.

Does precomputation of the first 100001 numbers’ factors give tle? While implementing sieve I stored the factors of all the 10^5 elements in a vector.Rest procedure is same as given above.still got tle.

1 Like

@anudeep2011:Can we solve this using Binary Indexed Trees?

1 Like

I have precomputed the factors and it can be done in linear time. Although my solution involves offline computation of answers. You can have a look at my approach here

@anudeep2011: Thank You for such a nice problem :slight_smile:

About the pre computation part, it is just like sieve, and can be easily done in linear time. It will actually save a lot of time while processing queries. Factoring is not a problem for this question, any method will work :slight_smile: As anudeep said, time limit was not strict if algo is right.

My approach was - making 9592 (no of Primes less than 100000) segment trees, each for a single prime. I then inserted the all multiples of the prime in its respective seg tree along with it’s index. When a query arrives, find its respective indices in all the seg trees which divides G (at max 6 factors so only 6 query in 6 diff trees). Find sol of respective tree and then combine.

I wonder if its possible to do this sum using sqrt decomposition. I have not implemented this but I think it’s possible.


I actually had to do precomputation in order to get AC. Without it was just getting TLE.

1 Like


I did with BIT. I change the query function to query in a range, but it runs in O(log^2 n).

Here is my solution:


@rodrigozhou Thanks.

edited but still getting wa someone plss help heres the modified link:

Here is my SQRT-Decomposition solution

And here is a solution using BIT

1 Like

Yes. Here is my SQRT-Decomposition solution

And here is a solution using BIT

1 Like

@anudeep2011 :sir plss tell me why im getting wa although the code seems to be working right on all the test cases i can think of

It is failing on a very large test case (n = 10^5)
For the query “63001 54725 59725” while the answer is “63001 11” your code last submission on codechef is giving “63001 22” as answer.

1 Like

@anudeep2011 Thanks. Missing this problem will haunt me and my future generations for eternity.


got AC thnx

Much Simpler Solution :slight_smile:

anudeep sir can you please explain how you handled the prime>350 part in your segment tree(authors) solution