P8764 [Lanqiao Cup 2021 National BC] Binary Problem

Xiaolan has been learning binary recently. He wants to know how many numbers from $1$ to $N$ have exactly $K$ `1`s in their binary representation. Can you help him?

Input one line containing two integers $N$ and $K$.

Output one integer representing the answer.

For $30\%$ of the testdata, $1 \leq N \leq 10^{6}, 1 \leq K \leq 10$. For $60\%$ of the testdata, $1 \leq N \leq 2 \times 10^{9}, 1 \leq K \leq 30$. For all testdata, $1 \leq N \leq 10^{18}, 1 \leq K \leq 50$. Lanqiao Cup 2021 National Contest, Group B Problem H (Group C Problem J). Translated by ChatGPT 5