Hide

Problem C
Difference

A smallest different sequence (SDS) is a sequence of positive integers created as follows: $A_1=r \geq 1$. For $n>1$, $A_ n=A_{n-1}+d$, where $d$ is the smallest positive integer not yet appearing as a value in the sequence or as a difference between two values already in the sequence. For example, if $A_1 =1$, then since $2$ is the smallest number not in our sequence so far, $A_2=A_1+2=3$. Likewise $A_3=7$, since $1, 2$ and $3$ are already accounted for, either as values in the sequence, or as a difference between two values. Continuing, we have $1, 2, 3, 4, 6$, and $7$ accounted for, leaving $5$ as our next smallest difference; thus $A_4=12$. The next few values in this SDS are $20, 30, 44, 59, 75, 96, \ldots $ For a positive integer $m$, you are to determine where in the SDS $m$ first appears, either as a value in the SDS or as a difference between two values in the SDS. In the above SDS, $12, 5, 9$ and $11$ first appear in step $4$.

Input

Input consists of a single line containing two positive integers $A_1$ $m$ ($1 \leq r \leq 100, 1 \leq m \leq 200\, 000\, 000$).

Output

Display the smallest value $n$ such that the sequence $A_1, \ldots , A_ n$ either contains $m$ as a value in the sequence or as a difference between two values in the sequence. All answers will be $\leq 10\, 000$.

Sample Input 1 Sample Output 1
1 5
4

Sample Input 2 Sample Output 2
1 12
4

Sample Input 3 Sample Output 3
5 1
2

Please log in to submit a solution to this problem

Log in