-1
$\begingroup$

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.
$\endgroup$
  • $\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
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.