2020ICPC 南京 K Co-prime Permutation（构造）

本文主要是介绍2020ICPC 南京 K Co-prime Permutation（构造），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
构造一个排列，使得$gcd(i,p_i)=1$的$p_i$数目严格为$k$。

思路：
因为$1$的存在，所以$k$一定不会是0。
因为$gcd(x,x+1)=1$，所以只需要交换相邻两个数就可以使得结果加2。
当$k$为奇数的时候使得$p_1=1$，然后后面的数相邻两个进行交换就好了。
当$k$为偶数的时候从1开始相邻两个数进行交换。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>using namespace std;
const int maxn = 2e3 + 7;
typedef long long ll;int main() {int n,k;scanf("%d%d",&n,&k);if(k == 0) {printf("-1\n");} else {if(k % 2 == 0) {for(int i = 1;i <= k / 2;i++) {printf("%d %d ",i * 2,i * 2 - 1);}for(int i = k + 1;i <= n;i++) {printf("%d ",i);}} else {printf("%d ",1);for(int i = 2;i <= k;i += 2) {printf("%d %d ",i + 1,i);}for(int i = k + 1;i <= n;i++) {printf("%d ",i);}}}return 0;
}

这篇关于2020ICPC 南京 K Co-prime Permutation（构造）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---