P13187 [GCJ 2016 Qualification] Coin Jam

Jamcoin 是一种长度为 $\mathrm{N}$（$\mathrm{N} \geqslant 2$）的二进制串，满足以下条件： - 每一位都是 $0$ 或 $1$。 - 首位为 $1$，末位也为 $1$。 - 无论将该串按 $2$ 到 $10$ 进制中的哪一种解释，所得的数都不是质数。 并非所有由 $0$ 和 $1$ 组成的串都是 jamcoin。例如，$101$ 不是 jamcoin，因为它在 $2$ 进制下的数值是 $5$，而 $5$ 是质数。但 $1001$ 是 jamcoin：在 $2$ 到 $10$ 进制下分别对应 $9, 28, 65, 126, 217, 344, 513, 730, 1001$，其中每一个都不是质数。 据说有些社区会用 jamcoin 作为货币。当你把 jamcoin 发送给别人时，礼貌的做法是为每个进制（$2$ 到 $10$）下 jamcoin 的数值都提供一个非平凡因子，以证明该 jamcoin 的合法性。（对于正整数 $K$，非平凡因子是指除了 $1$ 和 $K$ 之外的正整数因子。）为方便起见，这些因子需用 $10$ 进制表示。 例如，前述 jamcoin $1001$，对于 $2$ 到 $10$ 进制的解释，可以选择的非平凡因子分别为：$3, 7, 5, 6, 31, 8, 27, 5, 77$。 你能否生成 $\mathrm{N}$ 位、互不相同的 $\mathrm{J}$ 个 jamcoin，并且为每个 jamcoin 提供一组合法性证明？

输入的第一行是测试用例数量 $\mathrm{T}$。接下来有 $\mathrm{T}$ 组测试用例，每组一行，包含两个整数 $\mathrm{N}$ 和 $\mathrm{J}$。

对于每组测试用例，输出 $\mathrm{J}+1$ 行。第一行只包含 `Case #x:`，其中 $x$ 是测试用例编号（从 $1$ 开始）。接下来的 $\mathrm{J}$ 行，每行包含一个长度为 $\mathrm{N}$ 的 jamcoin，后跟九个整数，第 $i$ 个整数（$i$ 从 $1$ 开始）为该 jamcoin 在 $i+1$ 进制下的一个非平凡因子。 所有 jamcoin 必须互不相同。即使因子组不同，也不能输出相同的 jamcoin。

在样例中，为了便于说明，$\mathrm{N}$ 和 $\mathrm{J}$ 取了很小的值。注意，这组样例不会出现在 Small 或 Large 数据集中。 这只是众多合法解中的一种。你也可以用其他 jamcoin 及其因子组。补充说明： - $110111$ 不能作为输出，因为它在 $3$ 进制下为 $337$，而 $337$ 是质数。 - $010101$ 虽然 $10101$ 是 jamcoin，但不能作为输出，因为 jamcoin 必须以 $1$ 开头。 - $101010$ 也不能作为输出，因为 jamcoin 必须以 $1$ 结尾。 - $110011$ 也是 jamcoin，可以出现在输出中，但由于输出必须恰好有 $\mathrm{J}$ 个 jamcoin，不能再多输出。 - 对于样例输出的第一个 jamcoin，后面的第一个数不能是 $1$ 或 $35$，因为这两者是 $35$（$100011$ 在 $2$ 进制下）的平凡因子。 **限制条件** - $T = 1$。（只有一组测试数据。） - 保证存在至少 $J$ 个不同的长度为 $N$ 的 jamcoin。 **小数据集（10 分，测试集 1 - 可见）** - $N = 16$。 - $J = 50$。 **大数据集（20 分，测试集 2 - 隐藏）** - $N = 32$。 - $J = 500$。 注意，这道题不同于一般的 Code Jam 题目，你已经提前知道每个输入文件的内容。例如，小数据集的输入文件永远如下： ``` 1 16 50 ``` 因此，你可以在真正下载输入文件和开始计时之前，提前做一些计算。 翻译由 GPT4.1 完成。