算法标签

• 图论 (Graph Theory)
• 二分图染色 (Bipartite Coloring)
• 数论 (Number Theory)
• 质因数分解 (Prime Factorization)

题目解析

问题描述

给定一个数组，需要将元素染成两种颜色，使得对于任意两个同色元素 $x$ 和 $y$，如果 $x$ 整除 $y$，那么 $\frac{x}{y}$ 不能是质数。

换句话说，如果两个元素相差一个质因子倍数，它们不能同色。

核心思路

1. 建立冲突图

• 如果两个元素 $x$ 和 $y$ 满足 $x \mid y$ 且 $\frac{y}{x}$ 是质数，那么它们不能同色
• 这样的关系构成一个图，我们需要对这个图进行二分图染色

2. 关键观察

• 如果 $x$ 和 $y$ 相差一个质因子，那么它们之间有一条边
• 这个图实际上是二分图（题目保证存在解）
• 我们可以通过质因数分解来建立边的关系

3. 高效建图策略

由于 $n \leq 10^5$，$a_i \leq 10^6$，不能直接 $O(n^2)$ 建图。

优化方法：

• 对每个数进行质因数分解
• 对于每个数 $x$，考虑所有可能的质数 $p$，检查 $\frac{x}{p}$ 是否在数组中
• 如果存在，则在 $x$ 和 $\frac{x}{p}$ 之间建边
• 同样检查 $x \times p$ 是否在数组中（如果不超过 $10^6$）

4. 二分图染色

• 使用 BFS 或 DFS 进行二分图染色
• 从任意未染色节点开始，交替染色

算法步骤

1. 预处理：

   • 使用埃拉托斯特尼筛法预处理质数
   • 建立值到索引的映射

2. 建图：

   • 对每个数进行质因数分解
   • 对于每个质因子 $p$，检查相关数是否存在

3. 染色：

   • 使用 BFS 进行二分图染色
   • 输出染色结果

复杂度分析

• 时间复杂度：$O(n \log \max(a_i))$
• 空间复杂度：$O(n + \max(a_i))$

代码实现

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

const int MAX_A = 1e6 + 5;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> pos(MAX_A, -1);
    
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        pos[a[i]] = i;
    }
    
    // 筛法求质数
    vector<bool> is_prime(MAX_A, true);
    vector<int> primes;
    is_prime[0] = is_prime[1] = false;
    
    for (int i = 2; i < MAX_A; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (long long j = 1LL * i * i; j < MAX_A; j += i) {
                is_prime[j] = false;
            }
        }
    }
    
    // 建图
    vector<vector<int>> graph(n);
    
    for (int i = 0; i < n; i++) {
        int x = a[i];
        
        // 检查 x/p 是否存在（p 是质数）
        for (int p : primes) {
            if (1LL * p * p > x) break;
            if (x % p == 0) {
                int y = x / p;
                if (y < MAX_A && pos[y] != -1) {
                    graph[i].push_back(pos[y]);
                    graph[pos[y]].push_back(i);
                }
            }
        }
        
        // 检查 x*p 是否存在（不超过最大值）
        for (int p : primes) {
            long long y = 1LL * x * p;
            if (y >= MAX_A) break;
            if (pos[y] != -1) {
                graph[i].push_back(pos[y]);
                graph[pos[y]].push_back(i);
            }
        }
    }
    
    // 二分图染色
    vector<int> color(n, 0);
    
    for (int i = 0; i < n; i++) {
        if (color[i] != 0) continue;
        
        queue<int> q;
        q.push(i);
        color[i] = 1;
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            
            for (int v : graph[u]) {
                if (color[v] == 0) {
                    color[v] = 3 - color[u];  // 1->2, 2->1
                    q.push(v);
                }
            }
        }
    }
    
    // 输出结果
    for (int i = 0; i < n; i++) {
        cout << color[i] << " ";
    }
    cout << endl;
    
    return 0;
}

样例验证

样例1：[1, 2, 3, 4]

• 冲突关系：1-2（2/1=2是质数），2-4（4/2=2是质数）
• 染色：1→2，2→1，3→1，4→2
• 输出：2 1 1 2 ✓

样例2：[20]

• 只有一个元素，任意染色
• 输出：1 ✓