P17824 [COCI 2026/2027 #1] 有轨电车 / Tramvaj

某座城市的有轨电车网络可以看作均匀分布在一个圆周上的 $n$ 个车站。车站按顺时针顺序用正整数 $1$ 到 $n$ 编号。每两个车站之间恰有一条轨道，电车**始终沿顺时针方向行驶**。 一次长度为 $l$（$1 \le l \le n-1$）的乘车，会把你从当前车站送到沿顺时针方向前进 $l$ 站后到达的车站。 电车管理局**为每种乘车长度分别出售一种车票**。作为促销活动的一部分，他们决定给每种车票涂上颜色，并向满足以下条件的乘客赠送免费月票： - 经过若干次乘车后，**回到出发时所在的车站**； - 在这趟行程中使用的车票颜色**两两不同**。 管理局的老板们喜欢给车票涂色这种促销手段，却不希望有人免费乘车。因此，他们只会接受**没有任何人能够赢得免费月票**的涂色方案。 当然，可以把所有车票都涂成同一种颜色，但这样公众立刻就会发现根本不可能赢得免费月票。老板们并不在意虚假宣传的问题，他们要求你给出一个使用**尽可能多种颜色**的涂色方案！

第一行包含一个正整数 $t$（$1 \le t \le 1000$），表示情景的数量。 接下来 $t$ 行，每行包含一个正整数 $n$（$2 \le n \le 2\cdot 10^5$），表示该情景中电车网络的车站数量。 所有情景的 $n$ 之和不超过 $2\cdot 10^5$。

对于每个情景，按输入顺序输出两行。 第一行输出一个正整数 $k$，表示为车票涂色所使用的颜色数量。 第二行输出 $n-1$ 个用空格分隔的数 $c_1,\ldots,c_{n-1}$，其中 $c_i$ 表示长度为 $i$ 的乘车所对应车票的颜色。每种颜色必须是集合 $\{1,2,\ldots,k\}$ 中的一个正整数，并且**该集合中的每个数都必须至少出现一次**。

对于每个情景，设你的程序输出的颜色数量为 $k$，最多可以使用的颜色数量为 $k_{\mathrm{opt}}$。如果某个情景中输出的涂色方案不满足题目要求，那么该测试点得 **0 分**。 否则，对于每个情景，计算比例 $$ r=\begin{cases} 1, & \text{若 } k_{\mathrm{opt}}=1 \text{ 且 } k=1,\\ \dfrac{k-1}{k_{\mathrm{opt}}-1}, & \text{若 } k_{\mathrm{opt}}>1. \end{cases} $$ 一个测试点的得分比例为其中所有情景的**比例 $r$ 的最小值**。一个子任务的得分为该子任务的满分乘以该子任务所有测试点的得分比例的最小值。 | 子任务 | 分值 | 附加限制 | | --- | --- | --- | | 1 | 20 | $n \le 12$。 | | 2 | 10 | $n$ 是质数。 | | 3 | 15 | $n$ 是 $2$ 的幂。 | | 4 | 65 | 无附加限制。 |