[Solved]: number of subsets where GCD equals to X

Problem Detail: 

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.

Asked By : Alex Stack

Answered By : emmy

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/48576