#6350. 「CodePlus 2018 4 月赛」组合数问题

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: Snakes

题目描述

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

输入格式

从标准输入读入数据。

第一行两个整数 x,kx,k

输出格式

输出到标准输出。

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

样例

样例输入

6 2

样例输出

3 1
3 2

数据范围与提示

对于 20%20\% 的数据,k=1k=1

对于另外 20%20\% 的数据,x100x\leq 100

对于另外 20%20\% 的数据,k=2k=2

对于 100%100\% 的数据,1x109,1k1031\leq x\leq 10^9,1\leq k\leq 10^3


来自 CodePlus 第 4 次月赛,清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit:idea 与命题/钟皓曦 验题/何昊天
Git Repo:https://git.thusaac.org/publish/CodePlus4
感谢腾讯公司对此次比赛的支持。