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?