백준 13018: 특이한 수

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

13018번: 특이한 수열

 

골드3 난이도의 수학 분류 문제다.

 

이 문제의 핵심은 바로 임의의 자연수 N에 대해 N과 N+1은 서로소라는 것에 있다.

 

 

i와 A[i]가 서로소가 아닌 게 k개로 서로소인 게 n-k인 것이다. 이 때 n-k를 p라고 하자.

 

1은 모든 수랑 서로소이기도 하다.

그러면 숫자를 이런식으로 1씩 밀려 쓰면

1 2 3 4 5

2 3 4 5 1

이러면 모든 i에 대해 A[i]와 i가 서로소가 된다.

 

1부터 p까지 모든 수에 대해서만 이렇게 밀려 쓰면 된다. 그 뒤 모든 수들은 밀려쓰지 않고 그대로 쓰면 된다.

이를테면 n=7, k=2, p=5인 경우에

 

1 2 3 4 5 6 7

2 3 4 5 1 6 7

 

이러면 1~5까지만 밀려 쓴 뒤 i가 6, 7일 때만 i와 A[i]가 서로소가 아니게 된다.

 

다만 p=0인 경우 Impossible이 된다.

i가 1일 때는 무조건 서로소라서 서로소인 경우가 0개가 될 수는 없다.

 

다음은 C언어로 구현한 것이다.

int main()
{
	int n, k;
	scanf("%d %d", &n, &k);
	int p = n - k;
	if (p == 0)
	{
		printf("Impossible");
		return 0;
	}
	for (int i = 1;i < p;i++)
		printf("%d ", i + 1);
	printf("1 ");
	for (int i = p + 1;i <= n;i++)
		printf("%d ", i);
}