[TJOI2011] 卡片

题目解析

我们有 $m$ 张蓝色卡片和 $n$ 张红色卡片，每张卡片上有一个大于 1 的整数。每次可以拿走一张蓝色卡片和一张红色卡片组成一组，要求这两张卡片上的数字最大公约数大于 1。问最多可以拿走多少组卡片。

关键点

每次只能拿走一蓝一红两张卡片
这两张卡片的数字必须有公共的质因数（因为 gcd > 1）
每张卡片只能被使用一次

问题转化

这是一个典型的二分图最大匹配问题：

左侧：所有蓝色卡片
右侧：所有红色卡片
边：如果蓝色卡片 $b_i$ 和红色卡片 $r_j$ 的 gcd > 1，则它们之间有一条边

我们需要找到最多的匹配对数。

算法设计

方法一：直接建图 + 最大流（代码1）

这是最直观的方法，直接将蓝色卡片和红色卡片作为二分图的两部分，用最大流求解。

建图方式：

graph LR
    S(源点) --> B[蓝色卡片] --> R[红色卡片] --> T(汇点)

源点 S 连接所有蓝色卡片，容量为 1
所有红色卡片连接汇点 T，容量为 1
如果蓝色卡片 i 和红色卡片 j 的 gcd > 1，则从蓝色 i 到红色 j 连一条容量为 1 的边

复杂度分析：

节点数： $m + n + 2 ≈ 1002$
边数：最坏 $m × n = 250,000$ （当 m=n=500 时）
使用 Dinic 算法，在二分图中的复杂度约为 $O(E√V) ≈ 250,000 × √1000 ≈ 8 × 10^6$

这个方法虽然简单，但边数较多，在 T=100 组数据时可能达到临界。

方法二：质因数分解优化建图（代码2）

更高效的方法是利用质因数作为中间节点。

核心思想： 两张卡片匹配的条件是它们有公共质因数。我们可以通过质因数节点来连接蓝色和红色卡片。

建图方式：

graph TD
    S(源点 S) --> B1[蓝色卡片1]
    S --> B2[蓝色卡片2]
    B1 --> P1[质因数 p1]
    B1 --> P2[质因数 p2]
    B2 --> P1
    P1 --> R1[红色卡片1]
    P1 --> R2[红色卡片2]
    P2 --> R2
    R1 --> T(汇点 T)
    R2 --> T

源点 S → 每张蓝色卡片（容量 1）
蓝色卡片 → 该卡片数字的所有质因数节点（容量 1）
质因数节点 → 拥有该质因数的红色卡片（容量 1）
红色卡片 → 汇点 T（容量 1）

为什么这样是正确的？

从 S 到 T 的一条流路径代表一组匹配：S → 蓝色 → 质因数 → 红色 → T
只有当蓝色和红色有公共质因数时，才可能存在这样的路径
每条边容量为 1，保证了每张卡片只被使用一次

!!! 质数这一层条件了一个 blue 选择 red 的限制条件 : 拥有同一个质因子:

这是一种通用的有条件的二分图匹配的处理方式

优点：

边数大大减少：每张卡片最多有 8 个质因数（因为 $2×3×5×7×11×13×17×19 > 10^7$ ）
总边数从 $O(mn)$ 降到 $O((m+n)×8)$

代码解析（以优化版本为例）

1. 预处理质数表

cpp

void get_primes_euler(int n) {
    is_composite.assign(n+5,0);
    primes.clear();
    for (int i = 2; i <= n; i++) {
        if (!is_composite[i]) primes.push_back(i);
        for (int p : primes) {
            if (1LL * p * i > n) break;
            is_composite[i * p] = true;
            if (i % p == 0) break;  // 关键优化
        }
    }
}

使用欧拉筛法，时间复杂度 $O(n)$
筛到 $10^7$ ，因为卡片数字最大为 $10^7$

2. 质因数分解

cpp

void get_factors(int x) {
    facs.clear();
    for (int p : primes) {
        if (p * p > x) break;  // 只需检查到 sqrt(x)
        if (x % p == 0) {
            facs.push_back(p);
            while (x % p == 0) x /= p;  // 除尽该质因数
        }
    }
    if (x > 1) facs.push_back(x);  // 剩余的大质数
}

只使用预处理好的质数表进行试除
时间复杂度 $O(\text{质数个数}) ≈ O(\sqrt{10^7})$

3. 网络流建图

cpp

// 节点编号分配
int s = 0, t = 1;  // 源点、汇点
int blue_start = 2;  // 蓝色卡片从 2 开始
int red_start = m + 2;  // 红色卡片
int prime_start = m + n + 2;  // 质因数节点动态分配

// 蓝色卡片：S → Blue
for (int i = 1; i <= m; i++) {
    dinic.addEdge(s, blue_start + i - 1, 1);
    // 分解质因数，连接 Blue → Prime
    get_factors(blue_val);
    for (int p : facs) {
        if (!p_to_id.count(p)) 
            p_to_id[p] = prime_start++;  // 新质因数节点
        dinic.addEdge(blue_start + i - 1, p_to_id[p], 1);
    }
}

// 红色卡片：Prime → Red → T
for (int i = 1; i <= n; i++) {
    dinic.addEdge(red_start + i - 1, t, 1);
    get_factors(red_val);
    for (int p : facs) {
        if (!p_to_id.count(p))
            p_to_id[p] = prime_start++;
        dinic.addEdge(p_to_id[p], red_start + i - 1, 1);
    }
}

4. 最大流计算

使用 Dinic 算法计算从 S 到 T 的最大流，即为最大匹配数。

复杂度分析

步骤	时间复杂度	说明
预处理质数表	$O(10^7)$	只需执行一次
每组数据分解质因数	$O((m+n) × \sqrt{10^7})$	每张卡片分解约 446 次试除
网络流 Dinic	$O(E√V)$	节点数约 9000，边数约 9000

总复杂度在可接受范围内，能通过 T=100 组数据。

关键细节

质因数去重：分解质因数时，同一个质因数只记录一次
质因数节点共享：不同卡片可能有相同质因数，使用 map 记录质因数对应的节点编号
大质数处理：如果试除后剩下的数 > 1，它本身也是质因数
数组大小：合理估算最大节点数和边数，避免 RE

示例分析

以样例第一组数据为例：

4 3
2 6 6 15
2 3 5

质因数分解：

蓝色：2→{2}, 6→{2,3}, 6→{2,3}, 15→{3,5}
红色：2→{2}, 3→{3}, 5→{5}

可能的匹配：

蓝色2(6) ↔ 红色2(3) [通过质因数3]
蓝色3(6) ↔ 红色2(3) [通过质因数3]
蓝色4(15) ↔ 红色3(5) [通过质因数5]
蓝色1(2) ↔ 红色1(2) [通过质因数2]

但每张红色卡片只能匹配一次，所以最大匹配为 3。

总结

这道题的关键在于：

将卡片匹配问题转化为二分图最大匹配
使用质因数作为中间节点优化建图，减少边数
熟练掌握质因数分解和网络流算法

通过这种方法，即使 m,n 达到 500，也能高效求解。

代码 1

cpp

/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2026-01-12 20:04:52
 * Problem: P2065 [TJOI2011] 卡片 (GCD 朴素连边版)
 * Algorithm: Max Flow (Dinic) + Brute Force GCD
 */

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

// 点数：500 (蓝) + 500 (红) + 源汇 ≈ 1005
const int maxn = 1005; 
// 边数：最坏情况每对都连边 500*500 = 250,000。
// 网络流存双向边，所以数组要开到 500,000 以上
const int maxe = 600005; 
const long long INF = 1e18;

// --- 存图模板 ---
struct linkList {
    typedef struct {int u,v,w,next;} edge;
    edge e[maxe];
    int h[maxn],edge_cnt=0;
    linkList(){
        reset();
    }

    void reset() {
        edge_cnt=0;
        memset(h,-1,sizeof(h));
    }

    void add(int u,int v,int w=0){
        e[edge_cnt] = {u,v,w,h[u]};
        h[u] = edge_cnt++;
    }
    
    edge& operator[](int i){ return e[i]; }
} e;

// --- Dinic算法模板 ---
struct Dinic {
    vector<int> level, cur;
    int n;
    
    void init(int n) {
        e.reset(); // 清空边
        level.resize(n+5);
        cur.resize(n+5);
        this->n = n;
    }
    
    void addEdge(int u, int v, int cap) {
        e.add(u, v, cap);    // 正向边
        e.add(v, u, 0);      // 反向边
    }
    
    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[s] = 0;
        q.push(s);
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            
            for(int i = e.h[u] ; ~i ;i = e[i].next) {
                int v = e[i].v, cap = e[i].w;
                if (cap > 0 && level[v] < 0) {
                    level[v] = level[u] + 1;
                    q.push(v);
                }
            }
        }
        return level[t] >= 0;
    }
    
    long long dfs(int u, int t, long long preFlow) {
        if (u == t || preFlow == 0) return preFlow;
        long long flow = 0;
        
        for (int& cid = cur[u]; cid != -1; cid = e[cid].next) {
            int v = e[cid].v;
            int cap = e[cid].w;
            
            if (level[u] + 1 != level[v] || cap <= 0) continue;
            
            long long tr = dfs(v, t, min(preFlow, (long long)cap));
            
            if (tr == 0) continue;

            e[cid].w -= tr;
            e[cid ^ 1].w += tr;
            flow += tr;
            preFlow -= tr;
            if (preFlow == 0) break;
        }
        return flow;
    }
    
    long long maxFlow(int s, int t) {
        long long flow = 0;
        while (bfs(s, t)) {
            for (int i = 0; i <= n; i++) cur[i] = e.h[i];
            flow += dfs(s, t, LLONG_MAX);
        }
        return flow;
    }
} dinic;

// 全局变量
int m, n;
vector<int> blue_vals;
vector<int> red_vals;

void solve() {
    cin >> m >> n;
    
    blue_vals.resize(m);
    for(int i = 0; i < m; ++i) cin >> blue_vals[i];
    
    red_vals.resize(n);
    for(int i = 0; i < n; ++i) cin >> red_vals[i];

    // 节点分配规划:
    // S = 0
    // Blue Cards: 1 ~ m
    // Red Cards: m+1 ~ m+n
    // T = m + n + 1
    
    int s = 0;
    int t = m + n + 1;
    
    // 初始化 Dinic
    dinic.init(t + 1); 

    // 1. 构建源点 -> 蓝色卡片
    for (int i = 0; i < m; i++) {
        // 蓝色卡片编号: i + 1
        dinic.addEdge(s, i + 1, 1);
    }

    // 2. 构建红色卡片 -> 汇点
    for (int i = 0; i < n; i++) {
        // 红色卡片编号: m + 1 + i
        dinic.addEdge(m + 1 + i, t, 1);
    }

    // 3. 构建蓝色卡片 -> 红色卡片 (暴力枚举)
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // 如果两个数有公约数 (gcd > 1)，则可以匹配
            // __gcd 是 GCC 内置函数，也可以用 std::gcd (需 <numeric>)
            if (std::gcd(blue_vals[i], red_vals[j]) > 1) {
                // 连边: Blue(i+1) -> Red(m+1+j)
                dinic.addEdge(i + 1, m + 1 + j, 1);
            }
        }
    }
    
    cout << dinic.maxFlow(s, t) << endl;
}

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

代码 2

cpp

/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2026-01-12 20:04:52
 * Problem: P2065 [TJOI2011] 卡片
 * Algorithm: Max Flow (Dinic) + Prime Factorization
 */

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

// 点数预估：蓝色500 + 红色500 + 质数节点(动态)
// 边数预估：S->蓝 + 红->T + 蓝->质数 + 质数->红
const int maxn = 50005; 
const int maxe = 500005; 
const long long INF = 1e18;

// --- 存图模板 ---
struct linkList {
    typedef struct {int u,v,w,next;} edge;
    edge e[maxe];
    int h[maxn],edge_cnt=0;
    linkList(){
        reset();
    }

    void reset() {
        edge_cnt=0;
        memset(h,-1,sizeof(h));
    }

    //遍历点u 周围点
    template<typename U>
    void for_each(int u,U func){
        for(int i = h[u] ; i !=-1;i = e[i].next)
            func(e[i].u,e[i].v,e[i].w); //u v w
    }

    void add(int u,int v,int w=0){
        e[edge_cnt] = {u,v,w,h[u]};
        h[u] = edge_cnt++;
    }
    
    //下标访问
    edge& operator[](int i){ return e[i]; }
} e;

// --- Dinic算法模板 ---
struct Dinic {
    vector<int> level, cur;
    int n;
    
    void init(int n) {
        e.reset(); // 清空边
        level.resize(n+5);
        cur.resize(n+5);
        this->n = n;
    }
    
    // 添加边：从u到v，容量为cap
    void addEdge(int u, int v, int cap) {
        e.add(u, v, cap);    // 正向边
        e.add(v, u, 0);      // 反向边
    }
    
    // BFS分层
    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[s] = 0;
        q.push(s);
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            
            for(int i = e.h[u] ; ~i ;i = e[i].next) {
                int v = e[i].v, cap = e[i].w;
                if (cap > 0 && level[v] < 0) {
                    level[v] = level[u] + 1;
                    q.push(v);
                }
            }
        }
        return level[t] >= 0;
    }
    
    // DFS增广
    long long dfs(int u, int t, long long preFlow) {
        if (u == t || preFlow == 0) return preFlow;
        long long flow = 0;
        
        for (int& cid = cur[u]; cid != -1; cid = e[cid].next) {
            int v = e[cid].v;
            int cap = e[cid].w;
            
            if (level[u] + 1 != level[v] || cap <= 0) continue;
            
            long long tr = dfs(v, t, min(preFlow, (long long)cap));
            
            if (tr == 0) continue;

            e[cid].w -= tr;
            e[cid ^ 1].w += tr;
            flow += tr;
            preFlow -= tr;
            if (preFlow == 0) break;
        }
        return flow;
    }
    
    long long maxFlow(int s, int t) {
        long long flow = 0;
        while (bfs(s, t)) {
            for (int i = 0; i <= n; i++) cur[i] = e.h[i];
            flow += dfs(s, t, LLONG_MAX);
        }
        return flow;
    }
} dinic;

// --- 质数筛与分解工具 ---
// int primes[5000], p_cnt = 0;
// bool is_prime[5000];
//
// // 预处理 sqrt(10^7) ≈ 3162 内的质数
// void sieve() {
//     memset(is_prime, true, sizeof(is_prime));
//     is_prime[0] = is_prime[1] = false;
//     for (int i = 2; i < 5000; i++) {
//         if (is_prime[i]) primes[p_cnt++] = i;
//         for (int j = 0; j < p_cnt && i * primes[j] < 5000; j++) {
//             is_prime[i * primes[j]] = false;
//             if (i % primes[j] == 0) break;
//         }
//     }
// }

const int MAX_N = 1000000;  // 最大范围
std::vector<int> primes;
std::vector<bool> is_composite;
int p_cnt= 0;
// bool is_composite[MAX_N + 1];  // true 表示是合数

void get_primes_euler(int n) {
    // 初始化
    // for (int i = 0; i <= n; i++) is_composite[i] = false;
    is_composite.clear();
    is_composite.assign(n+5,0);
    primes.clear();
    
    for (int i = 2; i <= n; i++) {
        if (!is_composite[i]) primes.push_back(i);
        
        for (int j = 0; j < primes.size(); j++) {
            int p = primes[j];
            if (1LL * p * i > n) break;
            
            is_composite[i * p] = true;
            
            // 【核心关键】
            // 如果 i 被 p 整除，说明 i 的最小质因子就是 p。
            // 如果继续枚举下一个素数 p_next (p_next > p)，
            // 构造出的合数 X = i * p_next。
            // X 的最小质因子将会是 p (因为 i 包含因子 p)，而不是 p_next。
            // 这违背了"用最小质因子筛除"的原则，因此必须 break。
            if (i % p == 0) break;
        }
    }
}

// 分解质因数
vector<int> facs;
void get_factors(int x) {
    facs.clear();
    for (int i = 0; i < p_cnt && primes[i] * primes[i] <= x; i++) {
        if (x % primes[i] == 0) {
            facs.push_back(primes[i]);
            while (x % primes[i] == 0) x /= primes[i];
        }
    }
    if (x > 1) facs.push_back(x);
}

int m, n;
map<int, int> p_to_id; // 质数 -> 节点编号 映射
int node_cnt; // 当前节点总数分配器

void solve() {
    cin >> m >> n;
    
    // 节点分配规划:
    // S = 0
    // T = 1
    // Blue Cards: 2 ~ m+1
    // Red Cards: m+2 ~ m+n+1
    // Primes: 从 m+n+2 开始动态分配
    
    int s = 0, t = 1;
    node_cnt = m + n + 2;

    p_to_id.clear();
    
    // 初始化 Dinic，给一个较大的预估值，或者动态扩容
    // 因为这里不知道会有多少质数节点，先给个安全的上限，init 主要负责清空 head 数组
    dinic.init(maxn - 10); 

    // 1. 处理蓝色卡片
    for (int i = 1; i <= m; i++) {
        int val;
        cin >> val;
        int u = i + 1; // 蓝色卡片节点编号
        
        // S -> Blue
        dinic.addEdge(s, u, 1);
        
        // Blue -> Primes
        get_factors(val);
        for (int p : facs) {

            // 一个新的质数,还没有被记录
            if (p_to_id.find(p) == p_to_id.end()) {
                p_to_id[p] = node_cnt++;
            }
            int p_node = p_to_id[p];
            dinic.addEdge(u, p_node, 1);
        }
    }

    // 2. 处理红色卡片
    for (int i = 1; i <= n; i++) {
        int val;
        cin >> val;
        // int v = m + 1 + i + 1; // 红色卡片节点编号 (偏移 m+1)
        int v = m+ i +1;
        
        // Red -> T
        dinic.addEdge(v, t, 1);
        
        // Primes -> Red
        get_factors(val);
        for (int p : facs) {
            if (p_to_id.find(p) == p_to_id.end()) {
                p_to_id[p] = node_cnt++;
            }
            int p_node = p_to_id[p];
            dinic.addEdge(p_node, v, 1);
        }
    }

    // 经过中间层 `primes` 过滤后
    // 1. blue red 的配对 只能 选择 gcd(blue,red) >1 的
    // 2. !!!! 中间层 代表了 一种筛选条件 !!!
    
    // 更新 Dinic 的节点总数，用于循环边界优化
    dinic.n = node_cnt;

    cout << dinic.maxFlow(s, t) << endl;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    get_primes_euler(1e7+1); // 先预处理质数
    p_cnt = primes.size();
    

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

目录