# number of subsets where GCD equals to X

The original statement for this problem can be found here

This is a question from IEEExtream 2014. There is an array of integers given. Input is X, so output is the number of subsets where there GCD equals to X.

Eg:

OriginalSet = {2, 3, 5, 6, 6}
numberOfSubsets(2) => 3 // there are 3 subsets where their GCD equals to 2
i.e. {2, 6}, {2, 6}, {2, 6}


Limits:

OriginalSet.length < pow(10, 5),
element_of_an_array < pow(10, 4),
X < pow(10,4)


I bruteforced the solution and it gives me TLE. I am stuck on this question for few days now. Could you explain me how to solve this efficiently.

Edit

• the subset size is not limited to 2. It is from the power-set.
• It guarantees that for a given query there is only 100 unique numbers.
• I'm sure we had an almost identical question in the last couple of weeks but I can't find it right now. Anyone? Oct 22, 2015 at 11:28
• Last week there was a question about calculating the multiplication of the GCD of every possible subset. It was removed Oct 22, 2015 at 11:34
• @jjohn That sounds like it's the question I was thinking of, yes. Thanks! Oct 22, 2015 at 11:37
• Could you please identify constraints, i.e., X and the set size? Oct 22, 2015 at 17:32
• What's a "TLE", and why is it bad? What size of parameters? What have you tried?
– D.W.
Oct 22, 2015 at 21:07