题解：CF2123F Minimize Fixed Points
SkyWave
·
·
题解
前置知识、符号与约定
前置知识
符号与约定
文中用到的非公认或非常用的符号，按出现顺序排列：
-
[n]$：$\{1,2,3,\ldots ,n\}
-
$A \setminus B = \{x \mid x \in A \ \land \ x \not\in B \}
-
-
-
-
设 $\sigma = (a_1\ a_2\ \cdots\ a_k)$，则 $\operatorname{supp}(\sigma) = \{a_1, a_2, \dots, a_k\}
-
若 $\operatorname{supp}(\sigma) \cap \operatorname{supp}(\tau) = \emptyset$（文中仅出现了这种情况），设 $\sigma = (a_1 \cdots a_k) $，$ \tau = (b_1 \cdots b_m) $ ，则 $\sigma \circ \tau = (a_1 \cdots a_k)(b_1 \cdots b_m)
-
题意
给定 n，构造一个 [n] 上的置换 p，满足：
-
- 最小化 \sum_{i=1}^{n} [p(i) = i]。
报告任意一个 p。可以证明，p 总是存在的。
思路
观察 1：\sum_{i=1}^{n} [p(i) = i] 的下界
注意到
\forall\, i \in \{1\} \cup \mathbb{P} \cap \left[\left\lceil \frac{n}{2} \right\rceil, n\right], \quad p(i) = i
是无法避免的，因此这些位置已经被固定。
证明
而
$$
\forall\, i \in \mathbb{P} \cap \left[\left\lceil \frac{n}{2} \right\rceil, n\right], \quad p(i) = i
$$
**无法避免**是因为
$$
\forall\, i \in \mathbb{P} \cap \left[\left\lceil \frac{n}{2} \right\rceil,\, n\right],\quad \forall\, j \in [n] \setminus \{i\},\quad i \perp j$$
因为**最小**的，**不等于** $x$ 的，与 $x$ **不互质**的正整数是 $2x$。
因此， $\sum_{i=1}^{n} [p(i) = i]$ 的下界为 $\left|\{1\} \cup \mathbb{P} \cap \left[\left\lceil \frac{n}{2} \right\rceil, n\right]\right|$。
## 转换 1：最小化 $\sum_{i= 1}^{n} [p(i) = i]$ 的另一种表示
设 $p$ 的轮换分解为 $C_1 C_2 \dots C_k$。
若存在 $p$ 的轮换 $\sigma$ 满足 $\gcd(\operatorname{supp}(\sigma)) > 1$ 且 $|\sigma| > 1$，则有
$$
\forall\, x \in \operatorname{supp}(\sigma),\quad p(x) \not\perp x\ \land\ p(x) \ne x
$$
因此在
$$
\forall\, i \in [n] \setminus \{1\}, \quad p(i) \not\perp i
$$
的前提下，最小化
$$
\sum_{i= 1}^{n} [p(i) = i]
$$
可转换为，在
$$
\forall\, i \in [k], \quad \gcd(\operatorname{supp}(C_i)) > 1
$$
的前提下最小化
$$
\sum_{i= 1}^{k} \left[\left|C_i\right| = 1\right]
$$
## 观察 2：下界可以被取到
### 证明
若有
$$
\forall\, i \in [n] \setminus \left(\{1\} \cup \mathbb{P} \cap \left[\left\lceil \frac{n}{2} \right\rceil, n\right]\right), \ \text{包含}\ i \ \text{的轮换} \ \sigma \ \text{满足} \ \gcd(\operatorname{supp}(\sigma)) > 1 \ \land \ |\sigma| > 1
$$
则有下界可以被取到。
我们通过直接构造 $p$ 来证明：
$$
p = D_1 \circ \left(\prod_{i \in \mathbb{P} \cap [2, n]} D_i\right)
$$
其中：
- $D_1 = (1)$ 为平凡轮换
- $\forall \, i \in \mathbb{P} \cap [2,n]$，$D_i$ 为满足 $\operatorname{supp}(D_i) = \{ x \in [2,n] \mid P(x) =i \}$ 的轮换
因为有
$$
\forall\, i \in [n] \setminus \left(\{1\} \cup \mathbb{P} \cap \left[\left\lceil \frac{n}{2} \right\rceil, n\right]\right), \ \text{包含}\ i \ \text{的轮换} \ \sigma \ \text{满足} \ \gcd(\operatorname{supp}(\sigma)) \in \mathbb{P}
$$
所以有
$$
\forall\, i \in [n] \setminus \left(\{1\} \cup \mathbb{P} \cap \left[\left\lceil \frac{n}{2} \right\rceil, n\right]\right), \ \text{包含}\ i \ \text{的轮换} \ \sigma \ \text{满足} \ \gcd(\operatorname{supp}(\sigma)) > 1
$$
仍需证明
$$
\forall\, i \in [n] \setminus \left(\{1\} \cup \mathbb{P} \cap \left[\left\lceil \frac{n}{2} \right\rceil, n\right]\right), \ \text{包含}\ i \ \text{的轮换} \ \sigma \ \text{满足} \ |\sigma| > 1
$$
注意到有
$$
\forall\, i \in \mathbb{P} \cap \left[2, \left\lceil\frac{n}{2}\right\rceil\right
), \quad 2i \in [n] \ \land \ P(2i) = i
$$
综上所述，$p$ 符合题意要求，证毕。
# 算法&实现
## 算法
上述思路中，我们需要实现，将每个数按最大质因子“归类”。
对每个数因数分解以寻找其最大质因子，不是明智的做法。因为寻找因子是**困难**的，而寻找倍数是**简单**的。
以下伪代码展示了如何预处理每个 $i \in [n]$ 的最大质因子。
```
P[1] = P[2] = ... = P[n] = 0
for (i : 从大到小遍历 [1, n] 以内质数) {
for (j = i; j <= n; j += i) if (P[j] == 0) {
P[j] = i;
}
}
```
```P[1], P[2], ..., P[n]``` 即为所求，时间复杂度 $\Theta(n \log \log n)$，空间复杂度 $\Theta(n)$。
## 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 100000 + 1;
bitset<N> np;
vector<int> primes;
int p[N], cyc[N];
void solve() {
int n;
cin >> n;
for (auto itr = lower_bound(primes.begin(), primes.end(), (n + 1) >> 1, greater<>()); itr != primes.end(); ++itr) {
int i = *itr, len = 0;
for (int j = i; j <= n; j += i) if (!p[j]) {
cyc[len++] = j;
}
if (len) {
for (int j = 0; j < len; ++j) {
p[cyc[j]] = cyc[j + 1];
}
p[cyc[len - 1]] = cyc[0];
}
}
for (int i = 1; i <= n; ++i) {
cout << (p[i] ? p[i] : i) << ' ';
}
cout << '\n';
memset(p + 1, 0, sizeof(int) * n);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
for (int i = 2; i * i < N; ++i) if (!np[i]) {
for (int j = i * i; j < N; j += i) {
np[j] = true;
}
}
for (int i = 2; i < N; ++i) if (!np[i]) {
primes.push_back(i);
}
reverse(primes.begin(), primes.end());
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
```
## 复杂度分析
设 $N$ 为 $O(\max_{1 \leq i \leq t}{n_i})$。
上述代码时间复杂度为 $\Theta(N \log \log N + t \log \frac{N}{\log N} + \sum_{i=1}^t n_i \log \log n_i)$，空间复杂度为 $\Theta(N)$。
注意，若
```cpp
for (auto itr = lower_bound(primes.begin(), primes.end(), (n + 1) >> 1, greater<>()); itr != primes.end(); ++itr)
```
写成
```cpp
for (auto itr = primes.begin(); itr != primes.end(); ++itr)
```
则时间复杂度退化成 $\Theta(N \log \log N + t\frac{N}{\log N} + \sum_{i=1}^t n_i \log \log n_i)$。