OI题库

【题目描述】

万岁！特工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