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$

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?

  • $\begingroup$ Any chance you can rephrase that in a slightly clearer manner (for future generations to come)? $\endgroup$ – barak manos Feb 4 '15 at 15:52
  • $\begingroup$ @barakmanos updated!! $\endgroup$ – user123 Feb 4 '15 at 16:11
  • $\begingroup$ 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. $\endgroup$ – HammyTheGreek Feb 5 '15 at 5:55

Your Answer

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

Browse other questions tagged or ask your own question.