P9632 [ICPC2020 Nanjing R] K Co-prime Permutation 题解

Shunpower · 2023-09-10 18:28:40 · 题解

比较简单的构造题。

题意

构造一个长度为 n 的排列 p，满足存在恰好 k 个 i(1\leqslant i\leqslant n) 使得 \gcd(p_i,i)=1。

思路

首先可以想到互质的两种比较特殊的情况：

1. 两个相邻的奇数互质。

2. 两个相邻的数互质。

你发现这些性质都和相邻有关，自然想到交换相邻。这样做一次可以增加 2 个满足条件的位置。

考虑使用性质 2。如果从左往右依次交换 (1,2)(3,4)\cdots ，可以构造出非零偶数个互质位置。

奇数可以考虑保留 1，从左往右依次交换 (2,3)(4,5)\cdots，于是构造出了奇数个互质位置。

然后可以发现如果想要 k=0，因为 1 的存在，所以一定有一个位置是互质的，因此永远不可能做到 k=0。

于是 k 是奇数、非零偶数都构造出来了，k=0 时无解。