CF1332B Composite Coloring

一个正整数如果可以表示为两个大于 $1$ 的正整数的乘积，则称其为合数。例如，以下数字是合数：$6$、$4$、$120$、$27$。以下数字不是合数：$1$、$2$、$3$、$17$、$97$。 Alice 得到一个长度为 $n$ 的合数序列 $a_1,a_2,\ldots,a_n$。 她想选择一个整数 $m \le 11$，并将每个元素染成 $1$ 到 $m$ 之间的某种颜色，使得： - 对于每种颜色 $1$ 到 $m$，至少有一个元素被染成这种颜色； - 每个元素都被染色，且只能染成一种颜色； - 被染成同一种颜色的任意两个元素的最大公约数都大于 $1$，即对于每一对被染成同一种颜色的元素 $i,j$，都有 $\gcd(a_i, a_j)>1$。 注意，相等的元素可以染成不同的颜色——你只需为每个下标 $1$ 到 $n$ 的元素选择一种颜色即可。 Alice 已经证明，如果所有 $a_i \le 1000$，那么她总能通过选择某个 $m \le 11$ 来完成任务。 请你帮助 Alice 找到一种满足要求的染色方案。注意，你不需要最小化或最大化颜色数，只需找到一个 $1 \le m \le 11$ 的可行方案即可。

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 1000$），表示序列 $a$ 的长度。 第二行包含 $n$ 个合数 $a_1,a_2,\ldots,a_n$（$4 \le a_i \le 1000$）。 保证所有测试用例中 $n$ 的总和不超过 $10^4$。

对于每个测试用例，输出两行。第一行包含一个整数 $m$（$1 \le m \le 11$），表示使用的颜色数。颜色编号为 $1$ 到 $m$。 第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$（$1 \le c_i \le m$），其中 $c_i$ 表示第 $i$ 个元素的颜色编号。若有多种方案，输出任意一种均可。注意，你不需要最小化或最大化颜色数，只需找到一个 $1 \le m \le 11$ 的可行方案。 请记住，每种颜色 $1$ 到 $m$ 都至少要用一次。被染成同一种颜色的任意两个元素的最大公约数都必须大于 $1$。

在第一个测试用例中，$\gcd(6,10)=2$，$\gcd(6,15)=3$，$\gcd(10,15)=5$。因此，可以将所有元素染成同一种颜色。当然，在这个测试用例中还有其他满足 Alice 要求的染色方案。 在第二个测试用例中，每种颜色只有一个元素，因此染色方案一定满足 Alice 的要求。 由 ChatGPT 4.1 翻译