Codeforces 432C Prime Swaps：數論與貪心構造排序交換序列

題目大意

給定長度 n (≤ 10^5) 的排列，允許交換位置 i, j（i < j）當且僅當 j - i + 1 為質數。要求在 5n 次交換內將排列變為有序（升序），並輸出交換操作序列。

關鍵數論工具：哥德巴赫猜想

哥德巴赫猜想（強形式）：任意大於 5 的偶數可表示為兩個質數之和。
推論：任意大於 5 的整數 d 可表示為三個質數之和（若 d 為奇數，先取 3，剩餘偶數拆兩質數）。

這意味著：對於任意距離 d = j - i，我們可以用 ≤ 3 次質數長度跳躍將元素從 j 移動到 i。

貪心構造算法

1. 預處理篩法求出 n 以內所有質數，標記 isPrime[x]。
2. 建立值到位置的映射 pos[val]，目標有序數組 b 為 a 排序後結果。
3. 從左到右處理每個位置 i：目標值為 b[i]，當前位置 cur = pos[b[i]]。
   • 若 cur == i 繼續。
   • 否則，嘗試找一個中間位置 mid（i ≤ mid < cur），使得 cur - mid + 1 為質數。直接交換 mid 與 cur，更新映射，記錄操作。
   • 若無法一步到達，利用哥德巴赫拆解：先跳到某個 mid 使剩餘距離為質數，或用兩步質數跳躍。

代碼核心邏輯

vector primes;
vector isPrime(N, true);
void sieve() {
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i < N; ++i) if (isPrime[i]) {
        primes.push_back(i);
        for (long long j = 1LL*i*i; j < N; j += i) isPrime[j] = false;
    }
}

int main() {
    int n; scanf("%d", &n);
    vector a(n+1), b(n+1), pos(n+1);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]); b[i] = a[i]; pos[a[i]] = i;
    }
    sort(b.begin()+1, b.end());
    sieve();
    vector> ops;
    for (int i = 1; i <= n; ++i) {
        while (pos[b[i]] != i) {
            int cur = pos[b[i]];
            // 找一個 mid 使得 cur-mid+1 為質數
            for (int mid = i; mid < cur; ++mid) {
                if (isPrime[cur - mid + 1]) {
                    ops.emplace_back(mid, cur);
                    swap(a[mid], a[cur]);
                    pos[a[mid]] = mid; pos[a[cur]] = cur;
                    break;
                }
            }
        }
    }
    printf("%d\n", (int)ops.size());
    for (auto [x, y] : ops) printf("%d %d\n", x, y);
    return 0;
}

複雜度與操作數上界

• 篩法 O(n log log n)。
• 每個元素最多移動 O(log n) 步（實際上 ≤ 3 步），總操作數 ≤ 3n，滿足 5n 限制。
• 內層循環尋找 mid 可優化：預計算每個距離的最大質數跳躍，或直接從 cur 向左嘗試，實測極快。

總結

本題巧妙結合數論（質數分佈、哥德巴赫猜想）與貪心構造，將排序問題轉化為在質數長度約束下的元素移動，是構造類算法的佳作。