Pu++ Virtual Sessions 2


2020-07-12 07:48 AKDT

Pu++ Virtual Sessions 2


2020-07-12 09:48 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -69 days 18:11:26

Time elapsed


Time remaining


Problem B
Loo Rolls

Image by Karen Arnold from Pixabay.
Your friend Nick needs your help with a hard problem that he came across in real life. Nick has a loo roll of length $\ell $ centimetres in his bathroom. Every time he visits the toilet, he uses exactly $n$ centimetres of loo roll. When the roll runs out, Nick always goes to the store and buys a new one of length $\ell $ directly afterwards. However, sometimes the roll runs out even though Nick still needs a non-zero amount of paper. Let us call such an event a crisis.

Nick has a clever way of preventing crises from happening: he uses a backup roll. The backup roll is another roll of length $\ell $ that is hidden somewhere in the bathroom, and when the regular roll runs out even though Nick still needs more paper, he will take that amount from the backup roll. Then he will replace the regular roll directly after the visit.

As you can imagine, this makes crises much less frequent. But still, the backup roll will also slowly run out, and eventually a crisis might still happen. So to generalize this, Nick wants to use several layers of backup rolls. First he will take paper from roll number $1$ (the regular roll), if it runs out he will take from roll number $2$, then if roll $2$ runs out from roll number $3$, and so on all the way up to roll number $k$. After each visit, all the rolls that have run out will be replaced. Nick managed to prove that if he picks a large enough number $k$, he can actually make it so that crises never happen! Your task is to find the smallest such number $k$.


The input consists of a single line containing the two integers $\ell $ and $n$ ($1 \leq n \leq \ell \leq 10^{10}$).


Output the smallest integer $k$ such that crises will never happen when using $k$ layers of rolls (including the regular roll).

Sample Input 1 Sample Output 1
31 6
Sample Input 2 Sample Output 2
10000000000 17