P1582 Pouring Water

One day, CC bought $N$ bottles with effectively infinite capacity, each initially containing $1$ liter of water. Then CC found there were too many bottles, so he decided to keep at most $K$ bottles. Each time, he chooses two bottles that currently contain the same amount of water, pours all the water from one into the other, and then discards the empty bottle. (He cannot discard a bottle that still contains water.) Obviously, in some cases CC cannot achieve the goal, for example, $N = 3$, $K = 1$. In this case, CC will buy some new bottles (the new bottles have infinite capacity and initially contain $1$ liter of water) to achieve the goal. Now CC wants to know the minimum number of new bottles he needs to buy to achieve the goal.

One line containing two positive integers $N, K$ ($1 \le N \le 2 \times 10^9$, $K \le 1000$).

A non-negative integer indicating the minimum number of new bottles required.

Translated by ChatGPT 5