[ 백준 13018 ] 특이한 수열 (c/c++)

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

 

 

[ 문제 요약 ]

1부터 N까지 모든 수가 한 번씩 나오는 수열에서 gcd(i, A[i]) > 1 을 만족하는 i가 정확히 K개인 수열을 출력한다. 만약 조건을 만족하는 특이한 수열이 없다면 "Impossible" 을 출력한다.

 

 

[ 문제 풀이 ]

1. gcd(N, N) = N, gcd(N, N+1) = 1 이다.

2. 즉, 숫자를 하나씩 옆으로 밀게 되면 밀 숫자만큼 조건을 만족하는 숫자가 줄어든다.

3. gcd(N, 1) = 1 이기 때문에 K의 최대값은 N - 1 이 되기 때문에 K가 N 이상이라면 Impossible이다.

4. 조건을 만족하는 숫자가 1인 경우도 만들 수 없기 때문에 K가 1인 경우에도 Impossible이다.

 

 

[ 소스 코드 ]

#include <bits/stdc++.h>
using namespace std;

int N, K;
int arr[10101];

int main() {
    cin >> N >> K;
    if (K == 1 || N == K) cout << "Impossible";
    else {
        cout << N-K << " ";
        for (int i=1; i<N-K; i++) cout << i << " ";
        for (int i=N-K+1; i<=N; i++) cout << i << " ";
    }
    return 0;
}

 

 

 

[ 주의할 점 ]

gcd가 가지는 속성 중 gcd(N, N+1) = 1 을 잘 이용해서 풀면 된다.