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

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

@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.


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

@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

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

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

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.

1 Like

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,

@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;
    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?


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.

1 Like

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

Here is my solution if anyone wants to refer as I guess it’s pretty readable. Feel free to comment if anything isn’t clear. (PS: implemented after referring editorial :slight_smile:

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.

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

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: