Description

Xiaoming bought a high-end electronic watch and is getting ready to set the time.

In the M78 Nebula, the units of time are different from those on Earth: one hour in the M78 Nebula has $n$ minutes.

As everyone knows, the watch has only one button that can increase the current number by $1$. When setting the minutes, if the current displayed number is $0$, pressing the button once changes it to $1$, pressing again changes it to $2$. If the current number is $n-1$, then after pressing once it becomes $0$.

Because Xiaoming is very particular, he must set the watch to the exact correct time. If the time on the watch is $1$ minute ahead of the current time, then he needs to press the $+1$ button $n-1$ times to set it back to the correct time.

Xiaoming thinks it would be great if the watch could have one more button that adds $k$ to the current number.

He wants to know: if there is a $+k$ button, and he presses buttons using the optimal strategy, then from any minute value to any other minute value, what is the maximum number of button presses needed.

Note: when pressing the $+k$ button, if the number after adding $k$ exceeds $n-1$, it will be taken modulo $n$.

For example, when $n=10,k=6$, if the current time is $0$, then pressing the $+k$ button twice will set it to $2$.

Input Format

One line with two integers $n,k$, as described above.

Output Format

One line with one integer, meaning: using the optimal strategy, the maximum number of button presses needed to adjust from one time to another.

5 3

2

Hint

Sample Explanation

If the time is already correct, press $0$ times. Otherwise, the relationship between the number of presses and the sequence of operations is as follows:

1. +1
2. +1, +1
3. +3
4. +3, +1

Constraints

For $30\%$ of the testdata, $0<k<n \le 5$.

For $60\%$ of the testdata, $0<k<n \le 100$.

For $100\%$ of the testdata, $0<k<n \le 10^5$.

Time limit: 3 seconds, 256M. Lanqiao Cup 2018, the 9th National Final.

Translated by ChatGPT 5