题意简述

有一张 $n$ 个点的无向图，顶点 $u,v$ 之间有边当且仅当 $u \oplus v$ 是质数。求图的最小染色数及方案。

性质分析

两个数的 XOR 为奇数当且仅当它们奇偶性不同，为偶数当且仅当奇偶性相同。
除 $2$ 以外的质数都是奇数，因此仅考虑奇质数时，图是一个二分图（奇偶分层）。
但偶质数 $2$ 会产生边，例如 $1 \oplus 3 = 2$，$2 \oplus 4 = 2$ 等，这些边的两端奇偶性相同且相差 $2$。

最小颜色数

• $n = 1$ 时，显然 $1$ 种颜色。
• $n = 2$ 时，$1$ 和 $2$ 之间有边（$1\oplus2=3$），需要 $2$ 种颜色。
• $n = 3$ 时，$2$ 和 $3$ 之间无边，可以用 $2$ 种颜色（如 $1,2,2$）。
• $n = 4$ 时，需要 $3$ 种颜色。
• $n = 5$ 时，需要 $3$ 种颜色。
• $n \ge 6$ 时，最少需要 $4$ 种颜色。

构造方案（$n \ge 6$）

使用 $4$ 种颜色，按顶点编号模 $4$ 的余数染色：$c_i = (i-1) \bmod 4 + 1$。

证明：
若两个顶点同色，则它们的编号模 $4$ 同余，因此它们的 XOR 是 $4$ 的倍数。
唯一的偶质数是 $2$，但不能被 $4$ 整除；奇质数不可能被 $4$ 整除。
因此同色顶点之间的 XOR 不可能是质数，即不存在同色边。该染色合法。

对于 $n < 6$，可以直接使用预构造的最优方案。

复杂度

对于每组数据，输出 $O(n)$ 个整数。总复杂度 $O(\sum n) \le 2 \times 10^5$，非常快。

参考代码

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    if (n == 1) {
        cout << "1\n1\n";
    } else if (n == 2) {
        cout << "2\n1 2\n";
    } else if (n == 3) {
        cout << "2\n1 2 2\n";
    } else if (n == 4) {
        cout << "3\n1 2 2 3\n";
    } else if (n == 5) {
        cout << "3\n1 2 2 3 3\n";
    } else {
        // n >= 6，总是 4 色，按 mod 4 染色
        cout << "4\n";
        for (int i = 1; i <= n; ++i) {
            int c = (i - 1) % 4 + 1;
            cout << c << " \n"[i == n];
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}