 # Numways problem in inter iit contest2 hacker rank

@anton_lunyov I would like to know how you solved this problem problem link

Firstly think of the input as a graph : G(V,E) where V = {1,2…n} leaving the elements in set C ,
and E = (i,j) where i * a = j OR i * b = j OR i = j * a OR i = j * b (graph is undirected) .

Now we have to find the number of independent sets in this graph , which for general graphs has no polynomial time solution. So lets concentrate on the brute force approach for this problem.Simple brute force would be nothing but trying all subsets of the vertex set.However we can do better by decomposing the graph into connected components and doing the same for all these components.Also, a simple check will reveal that there a no more than 40 vertices in a single component for the constraints in the problem.This suggests us that we can try a meet in the middle approach.That is , we can compute those valid subsets of size of 20 elements and try finding the valid combinations .Another check will reveal that there are no more than 10^4 valid vertex subsets in the worst case . This suggests us that we can simply loop over the valid subsets using first 20 elements and check if the subset using the last 20 elements can be combined. This will give us a worst case of (10^8) iterations , which works quite fast.

Pseudo Code :

1. make the graph

2. find the components

3. for each component do :

4. Let the number of elements in the component be size

5. Now compute the list of all valid subsets L using the first size/2 elements.

6. Iterate through all valid subsets using the last (size - size/2) elements and for each such subset consider the number of subsets in L which on combination gives a valid independent set , and increase the count.

7. Multiply the count to the answer.