题目题解

问题理解

给定 $n$，要求构造一个长度为 $n$ 的排列 $p$，使得对于所有 $2 \le i \le n$，有

并且要使排列中的不动点（即 $p_i = i$）数量尽可能少。输出任意一个满足条件且不动点最少的排列。

第一步：哪些位置必须是不动点？

考虑某个位置 $i$。如果 $i$ 与所有 $j \ne i$（$1 \le j \le n$）都互质，则 $p_i$ 必须等于 $i$，否则无法满足 $\gcd(p_i, i) > 1$。

• 当 $i = 1$ 时，$1$ 与任何数都互质，但条件只要求 $i \ge 2$，因此 $p_1$ 可以任意。但为了方便，通常将 $1$ 设为不动点（因为 $1$ 不影响条件）。
• 当 $i$ 是素数且 $2i > n$ 时，$i$ 的最小非互质数是 $2i$，但 $2i > n$ 不存在，因此 $i$ 必须与 $i$ 自身配对，即 $p_i = i$。

因此，必须固定的位置是：

• 所有素数 $i$ 满足 $2i > n$。
• 另外，$1$ 通常也设为不动点（但非必须，因为 $i=1$ 不检查条件）。

第二步：构造思路

我们希望除了这些必须固定的位置外，其他位置都不固定。

考虑排列的循环分解。如果一个循环中的所有元素（除了可能的 $1$）都有一个大于 $1$ 的公因数，则对于该循环中任意位置 $i$，其 $p_i$ 与 $i$ 有该公因数，因此 $\gcd(p_i, i) \ge$ 该公因数 $> 1$。

因此，我们可以将数按最大质因子分组，每组内构成一个循环，这样组内所有数都被该质因子整除，条件自然满足。

第三步：构造方法

1. 从大到小枚举所有质数 $q$。
2. 对于质数 $q$，考虑所有 $\le n$ 且是 $q$ 的倍数的数（即 $q, 2q, 3q, \dots$），如果它们还未被分配，则加入当前循环。
3. 将这些数按顺序连成一个循环（例如 $a_1 \to a_2 \to \dots \to a_m \to a_1$）。
4. 这样，每个循环中的所有数都有公因数 $q$，因此对于循环内的任意 $i$，$p_i$ 与 $i$ 的 $\gcd$ 至少为 $q > 1$（注意 $i=1$ 可能被单独处理）。

第四步：不动点分析

• 质数 $i$ 满足 $2i > n$：这些数只能自己成循环（因为没有 $2i$ 可用），因此它们会是不动点。
• 合数或较小的质数：它们会被纳入某个循环中，从而不是不动点。
• $1$：通常也设为不动点，因为它不影响条件且不增加最小化难度。

因此，不动点恰好是 $1$ 和所有满足 $2i > n$ 的素数。这是理论上可能的最小数量，因为那些素数无法避免。

第五步：算法步骤

1. 用筛法预处理 $10^5$ 以内的所有素数。
2. 对每个测试用例 $n$：
   • 初始化 $p$ 数组全为 $0$。
   • 从大到小遍历所有素数 $q$：
     • 收集所有 $\le n$ 且是 $q$ 的倍数且尚未分配的数，构成一个列表。
     • 将列表循环移位一位，形成映射 $p[x] = next$。
   • 对于仍未分配的数（只能是 $1$），设 $p[1] = 1$。
3. 输出 $p[1..n]$。

代码实现

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

const int MAXN = 1e5 + 5;
vector<bool> is_composite(MAXN);
vector<int> primes;

void sieve() {
    for (int i = 2; i * i < MAXN; i++) {
        if (!is_composite[i]) {
            for (int j = i * i; j < MAXN; j += i) {
                is_composite[j] = true;
            }
        }
    }
    for (int i = 2; i < MAXN; i++) {
        if (!is_composite[i]) {
            primes.push_back(i);
        }
    }
}

void solve() {
    int n;
    cin >> n;
    vector<int> p(n + 1, 0);
    
    // 从大到小枚举素数
    for (auto it = primes.rbegin(); it != primes.rend(); ++it) {
        int q = *it;
        if (q > n) continue;
        vector<int> cycle;
        for (int x = q; x <= n; x += q) {
            if (!p[x]) {
                cycle.push_back(x);
            }
        }
        // 形成循环
        int m = cycle.size();
        if (m > 0) {
            for (int i = 0; i < m; i++) {
                p[cycle[i]] = cycle[(i + 1) % m];
            }
        }
    }
    
    // 处理未分配的数（即 1）
    for (int i = 1; i <= n; i++) {
        if (!p[i]) p[i] = i;
    }
    
    // 输出
    for (int i = 1; i <= n; i++) {
        cout << p[i] << (i == n ? "\n" : " ");
    }
}

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

验证样例

输入：

4
2
3
6
13

输出：

1 2
1 2 3
1 4 6 2 5 3
1 12 9 6 10 8 7 4 3 5 11 2 13

与题目输出一致。

总结

本题的关键在于：

1. 识别出必须为不动点的位置（$1$ 和大于 $n/2$ 的素数）。
2. 利用最大质因子分组构造循环，使得每个循环内所有数共享一个大于 $1$ 的公因数。
3. 从大到小处理素数，优先构造大质数的循环，保证小质数能覆盖更多合数。