Codeforces 449E Jzzhu and Apples 題解：數論構造最大匹配組數

題目大意

有 n 個蘋果，編號 1~n。需將其分組，每組**恰好 2 個**，且組內兩數的 **gcd > 1** (即不互質)。每個蘋果最多屬於一組。求**最大組數**並輸出任一最優分組方案。n ≤ 10⁵。

核心觀察：哪些數無法配對？

• 1：與任何數 gcd=1，無法配對。
• 大於 n/2 的質數 p：其倍數只有 p 和 2p，但 2p > n，故在 1~n 中**無其他倍數**可與之配對 (gcd>1 需公因數)。

**結論**：直接剔除 1 和所有 p > n/2 的質數，剩餘數字均可參與配對。

構造策略：按質因數分組配對

1. 篩法預計算所有質數及最小質因數。
2. 從大到小遍歷質數 p (僅考慮 p ≤ n/2)：
3. 收集所有**未被使用**的 p 的倍數 (p, 2p, 3p...)。
4. 若收集到的倍數個數為**奇數**，**捨棄 2p** (留給質數 2 統一處理)，其餘兩兩配對。
5. 若為偶數，直接兩兩配對。
6. 最後處理質數 2：收集所有剩餘未使用的偶數 (2 的倍數)，直接兩兩配對 (必為偶數個)。

為什麼捨棄 2p 而不是 p 或其他？

• 2p 同時是 2 的倍數，留給最後統一由 2 處理，不會浪費。
• p 是質數，只能與自身倍數配對，捨棄它會減少該質數組的配對數。
• 捨棄 2p 保證每個質數組內配對數最大化，且不影響質數 2 的最終配對。

完整 C++ 代碼 (AC)

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

const int MAXN = 100005;
int n;
bool used[MAXN];
int min_prime[MAXN];
vector primes;

void sieve() {
    for (int i = 2; i <= MAXN-1; ++i) {
        if (!min_prime[i]) {
            min_prime[i] = i;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (p > min_prime[i] || i * p >= MAXN) break;
            min_prime[i * p] = p;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    sieve();
    cin >> n;
    
    vector> ans;
    // 從大質數到小質數 (跳過 2)
    for (int i = primes.size() - 1; i >= 0; --i) {
        int p = primes[i];
        if (p == 2) break; // 最後處理 2
        if (p > n / 2) continue; // 大於 n/2 的質數無法配對，跳過
        
        vector multiples;
        for (int k = p; k <= n; k += p)
            if (!used[k]) multiples.push_back(k);
        
        if (multiples.size() % 2 == 1) {
            // 奇數個，捨棄 2p (必存在且未被使用，因 2p ≤ n 且 2p 是 2 的倍數，尚未處理)
            for (auto it = multiples.begin(); it != multiples.end(); ++it) {
                if (*it == 2 * p) { multiples.erase(it); break; }
            }
        }
        // 兩兩配對
        for (size_t j = 0; j + 1 < multiples.size(); j += 2) {
            ans.emplace_back(multiples[j], multiples[j+1]);
            used[multiples[j]] = used[multiples[j+1]] = true;
        }
    }
    
    // 處理質數 2：所有剩餘偶數
    vector evens;
    for (int k = 2; k <= n; k += 2)
        if (!used[k]) evens.push_back(k);
    for (size_t j = 0; j + 1 < evens.size(); j += 2) {
        ans.emplace_back(evens[j], evens[j+1]);
    }
    
    cout << ans.size() << '\n';
    for (auto [u, v] : ans) cout << u << ' ' << v << '\n';
    return 0;
}

複雜度分析

• 篩法：O(n log log n) 或線性篩 O(n)。
• 收集倍數：每個數最多被其最小質因數處理一次，總遍歷次數 ∑ n/p ≈ n log log n。
• 總時間：O(n log log n)，n=10⁵ 極快。
• 空間：O(n)。

關鍵細節避坑

1. 質數 2 必須最後處理**：因為它是所有偶數的公因數，統籌剩餘偶數配對。
2. 捨棄 2p 時需確保 2p 存在且未用**：p ≤ n/2 ⇒ 2p ≤ n，且 2 尚未處理，故 2p 必未被使用。
3. 輸出任意最優解**：題目允許任意最優分組，無需字典序最小。
4. n=1,2 時輸出 0**：代碼自然處理 (無質數 ≤ n/2，evens 為空或長度 1)。

數學證明草圖

構造演算法實際構建了一個**匹配**，其中每條邊連接兩個共享質因數的數。通過優先處理大質數並保留 2p 給 2，確保了：

• 每個質數 p > 2 的組內配對數最大化 (至多捨棄一個 2p)。
• 質數 2 獲得所有剩餘偶數，必為偶數個 (因總偶數個數 = ⌊n/2⌋，大質數組共消耗偶數個偶數，剩餘偶數)。
• 無法配對的數僅為 1 和大質數，這是理論下界。

結語

Codeforces 449E 是「數論洞見 + 貪心構造」的經典範例。核心突破點在於識別「大質數無法配對」並設計「捨棄 2p 留給 2」的巧妙策略，將看似複雜的圖匹配問題轉化為線性掃描的分組配對。此類「質因數分組 + 貪心配對」模式廣泛適用於 Codeforces/AtCoder 中涉及 gcd/lcm/互質條件的構造題。