# Condition for L and R to make the below scenario true?

You are a given a number N.

            N <= 10 ^ 9 .


You are given a range of numbers L and R .

               1 <= L , R <= 10 ^ 9.


You need to generate N by using numbers from L and R inclusive by adding them. You can use a number multiple times. For eg :

      test case : N  L  R
5   2   3    Yes N can be generated by using 2+3
7   4   5     NO , N can't be generated
45  9   11    Yes , using 9 five times
47  9   11    YES,  9*4 + 11 *1
48  9   11    Yes , 10*3 + 9*2
49  9   11    Yes , 9*1 + 10*4

-
You haven't actually asked a question. I don't count the title --- the question should be in the body, not just in the title. – Gerry Myerson Feb 27 '14 at 9:58

Assume $\gcd(L,R)=1$. We use the Extended Euclidean Algorithm to find $aL+bR=1$, where $a<0$. Then the solution is $$(aN+\lceil \tfrac{-aN}{R} \rceil R)L+(bN-\lceil \tfrac{-aN}{R} \rceil L)R=N$$ if $bN-\lceil \tfrac{-aN}{R} \rceil L$ is non-negative, otherwise a solution doesn't exist.

## How it works

We can assume $L$ and $R$ are coprime (otherwise we divide $L$, $R$, and $N$ by $\gcd(L,R)$; if $\gcd(L,R)$ does not divide $N$, no solution exists).

Using the Extended Euclidean Algorithm, we find two integers $a$ and $b$ such that $$aL+bR=1$$ or equivalently $$(aN)L+(bN)R=N.$$ However, one of $a$ or $b$ will be negative (which is not allowed in this problem, as demonstrated by the $(7,4,5)$ case). Assume $a$ is negative (otherwise swap $L$ and $R$).

If it is possible that $xL+yR=N$ where $x$ and $y$ are both positive, then $(aN-x)L+(bN-y)R=0$, implying $aN \equiv x \pmod R$. So, $x$ (if it exists) is equal to $aN+kR$ for some $k \geq 1$.

This implies $$(aN+kR)L+(bN-kL)R=N.$$ So, we choose the smallest $k$ for which $aN+kR \geq 0$, which is $k=\lceil \tfrac{-aN}{R} \rceil$. If $bN-kL<0$, then no solution exists (with two positive coefficients), otherwise the solution is as given above.

## Worked examples

• When $N=5$ and $L=2$ and $R=3$, we have $(-1) \times L + 1 \times R = 1$, so $a=-1$ and $b=1$. We have $k=\lceil \tfrac{-(-1) \times 5}{3} \rceil=2$, and since $bN-kL=1 \times 5-2 \times 2=1>0$, we have the solution $$\overbrace{1}^{aN+kR} \times \overbrace{2}^L+\overbrace{1}^{bN-kL} \times \overbrace{3}^R=\overbrace{5}^N.$$

• When $N=7$ and $L=4$ and $R=5$, we have $(-1) \times L + 1 \times R = 1$, so $a=-1$ and $b=1$. We have $k=\lceil \tfrac{-(-1) \times 7}{5} \rceil=2$, but $bN-kL=1 \times 7-2 \times 4=-1<0$, so no solution exists.

• When $N=49$ and $L=11$ and $R=9$, we have $(-4) \times L + 5 \times R=1$, so $a=-4$ and $b=5$. We have $k=\lceil \tfrac{-(-4) \times 49}{9} \rceil=22$, and since $bN-kL=5 \times 49-22 \times 11=3>0$, we have the solution $$\overbrace{2}^{aN+kR} \times \overbrace{11}^L+\overbrace{3}^{bN-kL} \times \overbrace{9}^R=\overbrace{49}^N.$$

-