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.


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}


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.


  • 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.
  • $\begingroup$ I'm sure we had an almost identical question in the last couple of weeks but I can't find it right now. Anyone? $\endgroup$ – David Richerby Oct 22 '15 at 11:28
  • $\begingroup$ Last week there was a question about calculating the multiplication of the GCD of every possible subset. It was removed $\endgroup$ – jjohn Oct 22 '15 at 11:34
  • $\begingroup$ @jjohn That sounds like it's the question I was thinking of, yes. Thanks! $\endgroup$ – David Richerby Oct 22 '15 at 11:37
  • 1
    $\begingroup$ Could you please identify constraints, i.e., X and the set size? $\endgroup$ – beginner1010 Oct 22 '15 at 17:32
  • $\begingroup$ What's a "TLE", and why is it bad? What size of parameters? What have you tried? $\endgroup$ – D.W. Oct 22 '15 at 21:07

See the solution for "585E - Present for Vitalik the Philatelist" here where is says "Let's calculate the number of subsets with gcd equal to 1". I hope you can extend the logic from there to solve the problem for X.

| cite | improve this answer | |

You can use dynamic programming approach to solve this problem; however, you have not yet specified what the limitation on X is. This is too similar to the question Algorithm for finding maximum mutually coprime subset of a multiset of integers In that way, you could also use GCD instead of LCM to solve your problem since the question I gave is a special case of your question.

| cite | improve this answer | |

Your Answer

