P7851 "JZOI-2" Signal Tower

All the members are thinking about organizing the anniversary celebration, but Xiao Xi just wants to slack off (moyu). Xiao Xi wants to watch TV, but he finds there is no signal, so he goes to fix the signal tower.

On a straight line with $10^{999}+1$ points, the distance between adjacent points on the line is the same. A signal tower is built at every point, numbered from left to right as $0 \sim 10^{999}$, where tower $0$ is the TV program transmission point. Since Xiao Xi only wants to watch TV, the signal here is transmitted only from left to right. Suppose a signal tower has strength $x$, then its signal can be transmitted at most a distance of $\lfloor\frac{x-1}{k}\rfloor$ to the right. Now Xiao Xi needs to set a strength for each signal tower, but there are too many towers and he cannot handle it, so he hands it to the "Benben robot" to do. The Benben robot sets the strength for each signal tower in the following way. First, set the strength of tower $0$ to $10^{30}$. Then, from left to right, start from signal tower $1$ and continue until signal tower $10^{999}$. For each signal tower, find the nearest signal tower $a$ on its left such that the signal of tower $a$ can be transmitted to this signal tower, and then assign this signal tower’s strength to be the distance between these two signal towers. Here, the distance between signal tower $i$ and signal tower $j$ is defined as $|i-j|$. For example, when $k=2$, the strengths of signal towers $1 \sim 5$ are $1,2,3,1,5$, respectively. However, Xiao Xi still does not trust the Benben robot, so he wants to know the strength of the $n$-th signal tower.

One line with two positive integers $n,k$. Their meanings are as described in the statement.

One line with one integer, indicating the strength of the signal tower with index $n$.

For $10\%$ of the testdata, $1\le n,k\le 2 \times 10^3$. For $30\%$ of the testdata, $1\le n\le 1 \times 10^7$. For another $15\%$ of the testdata, $k=1$. For another $15\%$ of the testdata, $k=2$. For $100\%$ of the testdata, $1\leq n\leq10^{18},1\leq k\leq10^{6}$. Translated by ChatGPT 5