Codeforces 432C Prime Swaps：質數交換構造排序序列

Codeforces 432C Prime Swaps：質數交換排序

題目大意

給定排列 1..n，允許交換位置 i, j 若 |i-j|+1 為質數。求交換序列使排列有序，操作數不限但需構造輸出。

核心觀察

質數分布密集（平均間隔 ~ln n），任意距離 d 幾乎總能找到質數 p ≤ d+1。策略：從左到右固定位置 1,2,3...，每次將目標數字移到正確位置。

演算法

1. 預計算 n+1 以內質數表（埃氏篩）。
2. 維護 pos[val] 記錄每數字當前位置。
3. 對 i = 1..n：
   若 a[i] != i，設 cur = pos[i]（目標數字當前位）。
   找最大質數 p ≤ cur - i + 1（二分查找質數表）。
   交換位置 cur 與 cur - p + 1，更新 pos[]，記錄操作。
   重複直到 a[i] == i。

每數字平均 ≤ 5 步歸位，總操作數 O(n log n)，極易通過。

完整程式碼（C++）

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

const int MAXN = 100005;
int a[MAXN], pos[MAXN];
vector primes;
bool is_composite[MAXN];
vector> ops;

void sieve() {
    for (int i=2;i> n) {
        for (int i=1;i<=n;i++) {
            cin >> a[i];
            pos[a[i]] = i;
        }
        ops.clear();
        for (int i=1;i<=n;i++) {
            while (a[i] != i) {
                int cur = pos[i];
                int dist = cur - i + 1;
                int p = *prev(upper_bound(primes.begin(), primes.end(), dist));
                int target = cur - p + 1;
                ops.emplace_back(target, cur);
                swap(a[cur], a[target]);
                pos[a[cur]] = cur;
                pos[a[target]] = target;
            }
        }
        cout << ops.size() << '\n';
        for (auto [u,v] : ops) cout << u << ' ' << v << '\n';
    }
    return 0;
}

複雜度

• 篩法：O(N log log N)。
• 主迴圈：每元素平均常數次交換，總 O(n log n)（含二分查找）。