专栏文章

题解：CF2123F Minimize Fixed Points

SSkyWave
CF2123F题解参与者 10已保存评论 10

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
10 条
当前快照
1 份
快照标识符
@miovsp1r
此快照首次捕获于
2025/12/03 01:58
3 个月前
此快照最后确认于
2025/12/03 01:58
3 个月前
查看原文

前置知识、符号与约定

前置知识

符号与约定

文中用到的非公认或非常用的符号，按出现顺序排列：
  • [n][n]：{1,2,3,…,n}\{1,2,3,\ldots ,n\}
  • A∖BA \setminus B：集合 AA 与集合 BB 的差
    A∖B={x∣x∈A ∧ x∉B}A \setminus B = \{x \mid x \in A \ \land \ x \not\in B \}
  • P(x)P(x) ：xx 的最大质因子
  • a⊥̸ba \not\perp b ：aa 与 bb 不互质
  • P\mathbb{P}：质数集
  • supp⁡(σ)\operatorname{supp}(\sigma)：轮换 σ\sigma 的支撑集
    设 σ=(a1 a2 ⋯ ak)\sigma = (a_1\ a_2\ \cdots\ a_k)，则 supp⁡(σ)={a1,a2,…,ak}\operatorname{supp}(\sigma) = \{a_1, a_2, \dots, a_k\}
  • σ∘τ\sigma \circ \tau：轮换 σ\sigma 与轮换 τ\tau 的乘积
    若 supp⁡(σ)∩supp⁡(τ)=∅\operatorname{supp}(\sigma) \cap \operatorname{supp}(\tau) = \emptyset（文中仅出现了这种情况），设 σ=(a1⋯ak)\sigma = (a_1 \cdots a_k) ，τ=(b1⋯bm)\tau = (b_1 \cdots b_m) ，则 σ∘τ=(a1⋯ak)(b1⋯bm)\sigma \circ \tau = (a_1 \cdots a_k)(b_1 \cdots b_m)
  • ∏\prod：轮换的连乘积

题意

给定 nn，构造一个 [n][n] 上的置换 pp，满足：
  1. ∀ i∈[n]∖{1},p(i)⊥̸i\forall\, i \in [n] \setminus \{1\},\quad p(i) \not\perp i；
  2. 最小化 ∑i=1n[p(i)=i]\sum_{i=1}^{n} [p(i) = i]。
报告任意一个 pp。可以证明，pp 总是存在的。

思路

观察 1：∑i=1n[p(i)=i]\sum_{i=1}^{n} [p(i) = i] 的下界

注意到
∀ i∈{1}∪P∩[⌈n2⌉,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
是无法避免的，因此这些位置已经被固定。

证明

p(1)=1p(1) = 1 无法避免是因为 11 与任何数都互质。
而
∀ i∈P∩[⌈n2⌉,n],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)$。

评论

共 10 条评论，欢迎与作者交流。

正在加载评论...