[백준 13018번] 특이한 수열 (C++)

https://www.acmicpc.net/problem/13018

이 문제는 특이한 수열 A를 찾는 문제이다. 특이한 수열의 성질은 다음과 같다.

• 수열 A의 길이는 n
• 1이상 n이하의 정수가 빠짐없이 모두 등장해야 하며, 각 수는 한번만 등장해야함
• 1 ≤ i ≤ n 인 i에 대해 gcd(i, A[i]) > 1 을 만족하는 i가 정확히 k개여야함

n, k 가 주어졌을 때, 특이한 수열을 아무거나 하나 구해보자.

---

gcd(i,A[i]) > 1을 만족하는 수는 i == A[i]이면 된다.

따라서 i == A[i]를 만족하는 수를 k개 출력하면 되고 나머지 인덱스와 원소의 관계는 서로소되야 한다.

i와 A[i]의 차가 1이거나 원소에 1이 있으면 항상 gcd(i,A[i]) = 1(서로소)을 만족한다.

 

1~N까지의 원소를 활용해야 하므로 1번째 인덱스로 인해 무조건 서로소가 하나 생길수 밖에 없다.

따라서 n == k일때가 impossible 한 경우다.

 

#include <iostream>
using namespace std;

int main() {
	int n, k;
	cin >> n >> k;
	if(n==k){
		cout << "Impossible";
		return 0;
	}
	cout << n-k << " ";
	for(int i = 1;  i < n-k; i++) cout << i << " ";
	for(int i = n-k+1; i <=n; i++) cout << i << " ";
}