PROBLEM LINK:Author: Anudeep Nekkanti DIFFICULTY: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 = p_{1}^k_{1} * p_{2}^k_{2} * ... * p_{i}^k_{i} * ... * p_{n}^k_{n}. We can call all p_{i} as X's factors (of course, p_{i}s are all different primes). For example, 18 = 2 * 3^2. So we can say that 18, has factors 2 and 3. Because p_{i} >= 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.
As analyzed before ,X has at most O(logX) factors. And each intervalmaximum 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. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 18 Mar '14, 20:44

@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
1
Yes. Here is my SQRTDecomposition solution http://www.codechef.com/viewsolution/3620495 And here is a solution using BIT http://www.codechef.com/viewsolution/3533495
(19 Mar '14, 13:58)
Much Simpler Solution :)
(19 Mar '14, 17:30)

Is there an alternate solution that does not involve the usage of segment tree ? answered 18 Mar '14, 20:49
One possible way is sqrt decomposition, but I think it may get TLE. Let me further think about it.
(18 Mar '14, 20:59)
I tried sqrt decomposition [ http://www.codechef.com/viewplaintext/3616120 ], it got TLE.
(18 Mar '14, 21:12)
1
Yes. Here is my SQRTDecomposition solution http://www.codechef.com/viewsolution/3620495 And here is a solution using BIT http://www.codechef.com/viewsolution/3533495
(19 Mar '14, 13:58)
5
@anudeep2011 Thanks. Missing this problem will haunt me and my future generations for eternity.
(19 Mar '14, 15:18)

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 answered 18 Mar '14, 22:08
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)
1
I actually had to do precomputation in order to get AC. Without it was just getting TLE.
(19 Mar '14, 00:38)

@anudeep2011:Can we solve this using Binary Indexed Trees? answered 18 Mar '14, 22:17
2
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
(19 Mar '14, 02:42)
@rodrigozhou Thanks.
(19 Mar '14, 06:42)
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)

@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

edited but still getting wa someone plss help heres the modified link: http://ideone.com/5EWVUQ answered 19 Mar '14, 13:15

@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 answered 19 Mar '14, 14:05
1
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)
got AC thnx
(19 Mar '14, 17:09)

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

@Anudeep, Sir can you please tell where my code fails http://www.codechef.com/viewsolution/3622900 answered 20 Mar '14, 14:01

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 answered 27 Mar '14, 17:13

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

@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 answered 06 Oct '15, 14:04
