小小的麻烦

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file codefeat.in Output file codefeat.out

【题目描述】

万岁!特工Bauer(见电视剧<24小时>——译者注)击毙了恐怖分子,炸掉了坏人的基地,拯救了人质,找到了隐藏在政府部门的间谍,避免了一场环境灾难,为三只流浪的小猫找到了家,所有这一切都发生在连续的19个小时之内。但现在,他只剩下5个小时来解决最重要的问题:一颗被密码保护的,已经激活的核弹。你能帮助他破解这个密码,使核弹无效吗?由真实事件改编(这是该电视剧的宣传语——译者注)。

CTU(Counter-Terrorist Unit,美国反恐局,电视剧中的虚构部门——译者注)的黑客们已经了解了有关这个密码的一些事实,但他们仍然没有完全破解它。他们知道密码是一个正整数。他们也掌握一些关于密码的线索,格式是“密码模X的余数在集合{Y1,Y2,...,Yk}中”。由这些线索可以解出多个解,但是密码很可能是最小的几个解之一。因此他们希望你按递增顺序输出最小的若干个解。

为了防止世界被破坏,为了守护世界的和平,贯彻真实的爱与邪恶,快来拯救世界吧!

【输入格式】

输入包含多组数据。

每组数据的第1行有2个正整数:C(1<=C<=9)和S(1<=S<=10),其中C是线索的数量,S是要求得到的解的数量。

接下来的C行,开头有两个正整数X(2<=X),k(1<=k<=100),接下来是k个不同的整数Y1,Y2,...,Yk(0<=Yi<X)。

每组数据保证所有的X两两互素(即没有1以外的公因数)。并且,所有的X都在32位无符号整数范围内。

输入结束标志为C=S=0.

【输出格式】

对于每组数据,输出S+1行。

包含S个最小的正整数解,按递增顺序排列。

第S+1行是一个空行。

【样例输入】

3 2
2 1 1
5 2 0 3
3 2 1 2
0 0

【样例输出】

5
13

【提示】

每个测试点中,数据组数<=10.

每组数据保证所有X的乘积,所有k的乘积均在64位带符号整数范围内。

【来源】

UVa11754 Code Feat

刘汝佳,《算法竞赛入门经典训练指南》表2.4