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

Larryyu · 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;

}