You are not logged in. Please login at to post your questions!


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.

This question is marked "community wiki".

asked 18 Mar '14, 20:44

shangjingbo's gravatar image

3★shangjingbo ♦♦
accept rate: 0%

edited 19 Mar '14, 13:56

anudeep2011's gravatar image


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


answered 18 Mar '14, 20:49

xorfire_'s gravatar image

accept rate: 0%

edited 18 Mar '14, 21:26

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

(18 Mar '14, 20:59) shangjingbo ♦♦3★

I tried sqrt decomposition [ ], it got TLE.

(18 Mar '14, 21:12) xorfire_3★

Yes. Here is my SQRT-Decomposition solution

And here is a solution using BIT

(19 Mar '14, 13:58) anudeep20116★

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

(19 Mar '14, 15:18) xorfire_3★

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.


answered 18 Mar '14, 22:08

ranjanvittal's gravatar image

accept rate: 0%

edited 18 Mar '14, 22:17

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

(18 Mar '14, 22:51) atulsehgal3★

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

(19 Mar '14, 00:38) junior944★

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


answered 18 Mar '14, 22:17

knb_dtu's gravatar image

accept rate: 22%

edited 18 Mar '14, 22:18



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:

(19 Mar '14, 02:42) rodrigozhou5★

@rodrigozhou Thanks.

(19 Mar '14, 06:42) xorfire_3★


I went through your code of ANUGCD solution using BIT. I didn't quite understand your BIT query logic to find the max in a range. How can a BIT be used to perform range maximum query?

Can you please explain?

(10 Jul '14, 00:32) sultanofswing6★

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

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 :) 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.


answered 18 Mar '14, 23:25

ashish1294's gravatar image

accept rate: 7%

edited 18 Mar '14, 23:27


Yes. Here is my SQRT-Decomposition solution

And here is a solution using BIT

(19 Mar '14, 13:58) anudeep20116★

Much Simpler Solution :)

(19 Mar '14, 17:30) ashish12942★

@anudeep2011 @xellos0 @rodrigozhou I did this question using the segment tree and prime factorisation and I am interested in the other methods for doing this problem mentioned by you above. So, I request you to explain your solution solution a bit more so that i and others can have benefit of that because it is quite difficult to understand the code directly.


answered 20 Mar '14, 22:58

ma5termind's gravatar image

accept rate: 11%


Just remember the usual query in BIT. It would be like this:

int query(const vector<int> &bit, int x) { int ret = 0; while (x > 0) { ret += bit[x]; x -= x & -x; } }

In the usual BIT query, bit[x] represents the accumulated sum in the range [x-(x&-x)+1, x]. That's why you do "x -= x & -x": you're jumping to the next range not summed yet.

So, the idea to do a range query in a BIT is to check if the whole interval that bit[x] represents is contained in the range that I want.

In the header of the range query function, the parameters means: v is the array of values, bit is the BIT of v and the range query is for [l, r].

In line, "int n = r - (r & -r)" means that bit[r] has the accumulated sum of the range [n+1, r]. As I have already decreased the value of l, if n >= l, then [n+1, r] is fully contained in (l, r] and I can sum bit[r] to my answer. Otherwise, I cannot do this. So I just get the value set in the v[r] and advance r in just one index.

I used the sum function in the explanation instead of max, and I hope it is not a problem.


answered 10 Jul '14, 05:43

rodrigozhou's gravatar image

accept rate: 0%


I understand and agree with your above explanation but I think it is valid only for range sum query and NOT min/max query.

Lets take an example (on an index 1 based BIT) for a range max query problem: This is my input array of size 4: index: 1 2 3 4 value: 5 3 1 4

This is the BIT constructed on the above input array which stores the max at each node according to your update function: index: 1 2 3 4 value: 5 5 1 5

How do I get the range max in the interval, say (2, 4) in this case with the above query algorithm?

Expected answer: 4

(10 Jul '14, 11:11) sultanofswing6★

So, you're doing query(v,bit,l=2,r=4).

In the first iteration, n=4-(4&-4)=0. So, n<l. This means the interval [1,4] is not contained in [2,4]. Therefore, I'll do ret=max(ret,v[4])=4 and r=3.

In the second iteration, n=3-(3&-3)=2 and n>=l. This means the interval [3,3] is contained in [2,4] and I can take the accumulated value in bit[3]. So, ret=max(ret,bit[3])=4 and r=2.

In the third iteration, n=2-(2&-2)=0 and n<l. This case is analogue to the first iteration and I'll do ret=max(ret,v[2])=4 and r=1.

This finishes the while loop and the answer is ret=4.

(10 Jul '14, 20:50) rodrigozhou5★

In fact, I think this works for any function... I don't see any restriction.

(10 Jul '14, 20:52) rodrigozhou5★


I just noticed that you were doing ret = max(ret, v[r--]) and not ret = max(ret, bit[r--]).

Now that I've understood it, I find your approach amazing! I was searching exactly for range min/max query using BIT for some time and I am glad that I came across your solution.

How did you come up with this approach? Have you considered writing an article on this? I doubt that many people know this.

(10 Jul '14, 21:49) sultanofswing6★

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


answered 19 Mar '14, 13:15

pawan55's gravatar image

accept rate: 0%

@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


answered 19 Mar '14, 14:05

pawan55's gravatar image

accept rate: 0%


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.

(19 Mar '14, 14:15) anudeep20116★

got AC thnx

(19 Mar '14, 17:09) pawan554★

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


answered 20 Mar '14, 12:47

architmittal's gravatar image

accept rate: 0%

@Anudeep, Sir can you please tell where my code fails


answered 20 Mar '14, 14:01

codemex's gravatar image

accept rate: 0%

I used Segment Tree and sparse tree in separate solution. My program was running in under 2s for the given constraints, but i kept getting TLE. Can you plz look at my solution,


answered 27 Mar '14, 17:13

akshayvats's gravatar image

accept rate: 0%

@anudeep2011 @rodrigozhou

Hi, I was going through the Binary Indexed Tree solution linked in the editorial. I could not quite understand how a BIT was used to perform range maximum query, specifically the following two blocks of update and query code:

void update(vector<int> &bit, int x, int val) { while (x < bit.size()) { bit[x] = max(bit[x], val); x += x & -x; } }

int query(const vector<int> &v, const vector<int> &bit, int l, int r) { int ret = 0; l--; while (r > l) { int n = r - (r & -r); if (n >= l) { ret = max(ret, bit[r]); r = n; } else { ret = max(ret, v[r--]); } } return ret; }

I haven't come across and do not know of a method to get max/min value in a range using BIT. The above method looks buggy to me too. Can you guys please explain the above approach?


answered 10 Jul '14, 00:54

sultanofswing's gravatar image

accept rate: 0%

edited 10 Jul '14, 01:24

@anudeep2011 Can't We do solve this question using Mo's Algorithm. I have tried it but getting TLE. Here is my code:


answered 06 Oct '15, 14:04

shishirt22's gravatar image

accept rate: 0%

edited 08 Oct '15, 00:43

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 18 Mar '14, 20:44

question was seen: 9,629 times

last updated: 08 Oct '15, 00:43