[Code+#4] 组合数问题

题目描述

众所周知,小葱同学擅长计算,尤其擅长计算组合数,所以小葱给了你两个数 $x$ 和 $k$,希望你把 $x$ 分成恰好 $k$ 个不同的组合数的和。所谓不同,即对于两个组合数 $C(n_1,m_1)$ 和 $C(n_2,m_2)$,如果 $n_1\neq n_2$​​ 或者 $m_1\neq m_2$​,我们就称这两个组合数是不同的。为了使得计算不过于复杂,你需要保证你给出的任何一个组合数 $C(n,m)$ 满足 $0\leq m\leq n\leq x$。数据保证一定有解。

输入输出格式

输入格式


从标准输入读入数据。 第一行两个整数 $x,k$。

输出格式


输出到标准输出。 $k$ 行,每行两个整数 $n,m$ 代表一个组合数 $C(n,m)$。如果有多种可能的答案,任意输出一组即可。

输入输出样例

输入样例 #1

6 2

输出样例 #1

3 1
3 2

说明

对于 $20\%$ 的数据,$k=1$。 对于另外 $20\%$ 的数据,$x\leq 100$。 对于另外 $20\%$ 的数据,$k=2$。 对于 $100\%$ 的数据,$1\leq x\leq 10^9,1\leq k\leq 10^3.$ Credit: https://www.luogu.org/discuss/show/38908