P4369 [Code+#4] Binomial Coefficient Problem

As we all know, Xiao Cong is good at calculations, especially at computing binomial coefficients. So Xiao Cong gives you two numbers $x$ and $k$, and wants you to express $x$ as the sum of exactly $k$ distinct binomial coefficients. By distinct, we mean that for two binomial coefficients $C(n_1, m_1)$ and $C(n_2, m_2)$, if $n_1 \neq n_2$ or $m_1 \neq m_2$, then these two binomial coefficients are considered different. To keep the computation from being too complex, you must ensure that every binomial coefficient $C(n, m)$ you provide satisfies $0 \leq m \leq n \leq x$. It is guaranteed that there is a solution.

Read from standard input. The first line contains two integers $x, k$.

Output to standard output. Output $k$ lines. Each line contains two integers $n, m$ representing a binomial coefficient $C(n, m)$. If multiple answers are possible, output any one of them.

For $20\%$ of the testdata, $k = 1$. For another $20\%$ of the testdata, $x \leq 100$. For another $20\%$ of the testdata, $k = 2$. For $100\%$ of the testdata, $1 \leq x \leq 10^9, 1 \leq k \leq 10^3$. Credit: https://www.luogu.org/discuss/show/38908 Translated by ChatGPT 5