I am trying to solve http://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.
You can delete a number from the set if a divisor of that number is present in the set too.
The maximum number of the remaining numbers in the set will be at most 5 then, so I think that optimization is sufficient to make your code pass in time.
Osama_Alkhodairy , Still getting TLE. Link to my code: http://codeforces.com/gym/101102/submission/37739183 Please have a look at it. Trying to solve this problem for last 4 days. I have generated all distinct LCMs possible for all subsets possible for 1 to 10. There are around 240 distinct values. So i Computed prefix sum for all 240 values for the given array and then deleted a number from set if it has a divisor present in the set. Then generated subsets and applied inclusion exclusion.
I can't view your code, so can you upload it on ideone or something alike?
However, I can see only 42 LCM distinct values,
Thanks for the help Osama_Alkhodairy. Got Accepted . I was doing a silly mistake while computing the LCM of subsets.