自动搬运

查看原文

来自洛谷，原作者为

	Larryyu Euphoric NocturNe |AS| ALTERing EGO

搬运于2025-08-24 22:50:16，当前版本为作者最后更新于2023-09-10 19:51:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Description

给定 $n$ 和 $k$，求一个 $n$ 的排列 $p_1,p_2\dots p_n$，使得有恰好有 $k$ 个 $i$，满足 $\gcd(i,p_i)=1$。

Solution

前置芝士：最大公约数 - OI Wiki (oi-wiki.org)

我们知道：$\gcd(a,b)=\gcd(b,a\bmod b)$

因此当 $a=b+1$ 时，$\gcd(a,b)=\gcd(b,a\bmod b)=\gcd(b,1)=1$。

所以对于任意一对相邻的数，它们的最大公约数为 $1$。

那我们在 $i\in [1,k-1]$ 的位置上放 $i+1$，在 $k$ 的位置放 $1$，在 $i\in[k+1,n]$ 的位置上放 $i$，就能满足条件。

对于 $k=0$ 的特殊情况，我们输出 -1 即可。

Code

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,k;
	cin>>n>>k;
	if(k==0) cout<<-1<<endl;
	else {
		for(int i=1;i<=k;i++){
			cout<<i%k+1<<" ";
		}
		for(int i=k+1;i<=n;i++){
			cout<<i<<" ";
		}
	}
	return 0;
	
}