What are the constraints for the number of elements and the values (a_i)?

I'd like to know more details (time limit, amount of numbers in array and constraints on the numbers), but anyway, I'll share the solution that came to mind.

• No number up to 10⁹ has more than 1344 divisors, so we can find divisors of every element of array and store a list of positions that divide every number. This may or may not fit in memory or time, depending on the constraints. This step is , where M is the maximum value an array element can take.
• Now for each query, make a list of the primes that divide Value. There are at most 9 such primes, because the product of the first 10 primes is  $>10^9$. Now for every possible mask of primes, check how many positions of range [L, R] divide their product with a binary search and use inclusion-exclusion principle. This process is O(2⁹  *  _logN) for each query, making the whole program O(Q * 2⁹ * _logN). This, again, may or may not fit in time depending on the constraints.

this problem is from codechef march long challange..

it still running dude, don't cheat

At first generate a list of primes that divide a number, for all number till M, the maximum number. This takes .

Now, for each number of the array a_i, lets say the primes p₁, p₂, ..., p_k divide that number, you can get this quickly from step 1. Go through all subsets of these primes. If a subset is p_i1, p_i2, ..., p_ir, then insert i to list pos_{pi1·pi2... pir}. This step takes O(2⁶n).

Now when you receive a query X, take the primes p₁, p₂, ..., p_k, that divides X, from the list generated at first. Now go through all of its subsets. Let the chosen subset be p_i1, p_i2, ..., p_ir, then count how many times a number from [l, r] appears in pos_{pi1·pi2... pir}. It can be done with two binary searches. If r is odd then add the count to answer, else subtract this count. It can be proven that this gives the answer, by inclusion-exclusion principal. Basically this counts number of numbers with at least one prime common with the query X. This step takes

Why are you upvoting this post? It is cheating, and this post should be deleted immediately, I think because it violates CodeChef rules and principles of the competitive programming.

You also can do it with bitset. numbers less than 10^5 has less than 7 prime divisors. So for every primes less than 1e5 set the bit of positions of those numbers which are divided by.

GCD(x, a[i]) has no common prime divisors If their GCD is 1. you can travel through prime divisors and check how many numbers you can divide in the given range. then the ans might be (r-l+1- NumberofSetBit).

you can solve it easily than other technique.