# ANUGCD - Editorial

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

Medium

### PREREQUISITES:

Segment Tree, Factorize

### PROBLEM:

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.

### EXPLANATION:

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.
Sqrt-Decomposition.
Binary Indexed Tree.
STL-MAP

### AUTHOR’S AND TESTER’S SOLUTIONS:

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

9 Likes

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.http://www.codechef.com/viewsolution/3536122

1 Like

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

1 Like

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

2 Likes

edited but still getting wa someone plss help heres the modified link: http://ideone.com/5EWVUQ

@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
http://ideone.com/5EWVUQ

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 http://www.codechef.com/viewsolution/3622900

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

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, http://www.codechef.com/viewsolution/3557742 http://www.codechef.com/viewsolution/3557556

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?

@sultanofswing

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

@anudeep2011
Can’t We do solve this question using Mo’s Algorithm. I have tried it but getting TLE.
Here is my code:https://www.codechef.com/viewsolution/8398234

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

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

I tried sqrt decomposition [ http://www.codechef.com/viewplaintext/3616120 ], 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: http://www.codechef.com/viewsolution/3533495

2 Likes