# Given an array, how many no. of subsequnces of array such that gcd of numbers in that subsequence will be between a and b

A sub-sequence can be obtained from the original sequence by deleting $0$ or more integers from the original sequence.

$L \le$ GCD(all numbers in subsequence) $\le R$

number of such sequences.

For example: say given array has $2$ numbers i.e. $1, 2.$ the possible subsequences are:
$1$
$2$
$1$ $2$

Now $gcd(1) = 1$
$gcd(2) = 2$
$gcd(1, 2) = 1$

$a$ and $b$ will be given integers. say $a = 1$ and $b = 2$
then the answer for : How many no. of subsequences of array have gcd in range $a$ to $b$ i.e. $1$ to $2$, will be 3

say $a= 1$ and $b= 1$ answer will be $2$...

Limit for number of integers in the given array is $50$. Maximum $50$ elements will be there in array.

How can I do it in most efficient way?

• Any chance you can rephrase that in a slightly clearer manner (for future generations to come)? – barak manos Feb 4 '15 at 15:52
• @barakmanos updated!! – user123 Feb 4 '15 at 16:11
• Is this and and your other recent question homework or a coding contest? If so, you should mark them as such. If not, some context (for both) of what your trying to solve (context) would be useful. – HammyTheGreek Feb 5 '15 at 5:55