B. Composite Coloring

Link

Solution

题目好长，但题意很简单，给一个合数数组a，用1-11中的数给该数组染色，要保证如果a[i]和a[j]颜色相同那么gcd(a[i], a[j])>1，输出用到的颜色数目和染色结果。至于把合数数组加粗的原因是本来还考虑了有素数元素的情况结果写着写着才意识到合数数组哪来的素数元素……

可以发现只要最小除数相同且不为1的合数（这些合数的gcd必然相等且大于1）染同一种颜色就行了。

Code

vector<int>pos[maxn];
int clr[maxn];

int aux(int x) {
    for (int i = 2; i <= x; i++)if (x%i == 0)return i;
}

int main(int argc, char **argv) {
    int n, t, tmp;
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 0; i <= 1000; i++)pos[i].clear();
        for (int i = 0; i < n; i++) { cin >> tmp; pos[aux(tmp)].push_back(i); }
        int color = 0;
        for (int i = 1; i <= 1000; i++)
            if (!pos[i].empty() && ++color)
                for (auto &j : pos[i])clr[j] = color;
        cout << color << endl;
        for (int i = 0; i < n; i++)cout << clr[i] << " ";
        cout << endl;
    }
    return 0;
}