1482. [UVa 11754] 数论难题

【题目描述】

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

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

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

【输入格式】

输入包含多组数据。

每组数据的第 $1$ 行有 $2$ 个正整数：$C(1 \leq C \leq 9)$ 和 $S(1 \leq S \leq 10)$，其中 $C$ 是线索的数量，$S$ 是要求得到的解的数量。

接下来的 $C$ 行，开头有两个正整数 $X(2 \leq X),k(1 \leq k \leq 100)$，接下来是 $k$ 个不同的整数$Y_1,Y_2,...,Y_k(0 \leq Y_i < 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

【提示】

每个测试点中，数据组数 $\leq 10$.

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

【来源】

UVa 11754 Code Feat

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