I am trying to solve http://mirror.codeforces.com/problemset/gymProblem/101102/J . The summarized form of the problem is as follows:

There are T testcases. In each testcase You are Given an array of size N and Q queries. (N,Q<=10^5).Array elements<=10^9 In each query you are given range [L,R] and a set of distinct integers lying in range [1,10]. Now for each query you have to report no. of elements in range [L,R] which are divisible by atleast one element from the set.

My approach:

I am storing a 2D prefix sum array which tells the no. of elements divisible by X(1<=X<=10) in range [L,R]. Now for a given query I am generating all subsets of elements in the set and then using inclusion-exclusion principle to find the numbers divisible by atleast 1 element from set. But getting TLE .

Please Suggest some optimization or some other approach to this problem Thanks in advance.