2022绍兴市初中组编程比赛-----问题 C: 染色(color) 题解

题目

问题 C: 染色(color)

题目描述

给你一个长度为 n 的序列 a，你需要依次把每个数染成红色或绿色，设 x 等于所有红色的数的乘积，y 等于所有绿色的数的乘积。一种染色方案是好看的当且仅当红色的数和绿色的数都至少有 1 个，并且 x 和 y 的最大公因数等于 1。
两种染色方案不同当且仅当存在一个数 ai 在两种方案里的颜色不同。
请你求出好看的染色方案数的二进制表示。

输入

第一行一个整数n；
第二行n个整数a1 …… an。

输出

一行一个整数，表示答案的二进制表示。

样例输入

1
2

3
1 2 3

样例输出

提示

样例输入2
4
19 19 8 10
样例输出2
10
样例1：除了全为绿色或者全为红色，其它均合法，答案为6，二进制表示为110。
样例2：（绿绿红红）和（红红绿绿）合法，答案为2，二进制表示为10。
【数据范围】
对于10%的数据，n≤2；
对于30%的数据，n≤15，ai≤15；
对于60%的数据，n≤10^3；
对于另外10%的数据，ai=1；
对于另外10%的数据，ai≤2；
对于所有数据，1≤n≤10^{5，1≤ai≤10}6。

题解

其实就是并查集，求出有几个集合就是关键了。
注意并查集以最初的因子为基础分的。

#include <bits/stdc++.h>
using namespace std;
int n,cnt,a[100005],t,mn[1000050],p[1000050],mx,f[1000050],mark[1000050];
void init(){
    for (int i = 2; i <= mx; i++){
        if (!mn[i]){
            mn[i] = i;
            p[++t] = i;
        }
        for (int j = 1; j <= t; j++){
            if (p[j] > mn[i] || p[j] > mx/i){
                break;
            }
            mn[p[j]*i] = p[j]; 
        }
    }
}
int find(int x){
    if (f[x] != x){
        f[x] = find(f[x]);
    }
    return f[x];
}
void mer(int x,int y){
    int a = find(x),b = find(y);
    if (a != b){
        f[b] = a;
    }
}
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    scanf("%d",&n);
    for (int i = 1; i <= n; i++){
        scanf("%d",&a[i]);
        mx = max(mx,a[i]);
    }
    init();
    for (int i = 1; i <= mx; i++){
        f[i] = i;
    }
    for (int i = 1; i <= n; i++){
        int v = a[i];
        if (v == 1){
            cnt++;
            continue;
        }
        int last = 0;
        while (v > 1){
            int now = mn[v];
            while(v%now == 0){
                v /= now;
            }
            if (last){
                mer(last,now);
            }
            last = now;
            mark[last] = 1;
        }
    }
    for (int i = 1; i <= mx; i++){
        if (mark[i] && f[i] == i){
            cnt++;
        }
    }
    for (int i = 1; i <= cnt-1; i++){
        printf("1");
    }
    printf("0");
    return 0;
}