[백준 2981] 검문 [C]

백준 - 2981

---

풀이

입력받은 N개의 수들이 M으로 나누었을 때, 나머지가 모두 동일하도록 하는 M을 구하는 문제이다.

단순하게 해결하기에는 정답 비율이 처참하다, 시간 초과를 생각해 효율적으로 M을 구하는 방법을 고안했다.

 

N개의 수들을 다음과 같이 표현할 수 있다.

arr[0] = M*q_0 + r

arr[1] = M*q_1 + r

arr[2] = M*q_2 + r

"

"

arr[N-1] = M*q_N-1 + r

 

M의 범위는 다음의 조건을 따른다.

• N >= 2일 때, 2번째 N보다 큰 M은 존재하지 않는다.
• (x = arr[1] - arr[0]) = M*(q_1 - q_0)이 성립하며, x의 약수 중에 N개의 수에 대해 만족하는 M이 존재한다.

x의 약수가 아니더라도 M이 될 수 있으므로, x를 포함한 x의 약수를 구하고 정렬 해주어야 한다.

int sq = sqrt(x);
for (int i = 2; i <= sq; i++)
    if (x%i == 0){
        M[idx++] = i;
        if (x/i != i) M[idx++] = x/i;
    }
qsort(M, idx, sizeof(int), compare);
M[idx++] = x;

 

구한 약수들을 이용해 나머지가 같은 경우에만 출력해주면 된다.

for (int i = 0, j; i < idx; i++){
    for (j = 1; j < N; j++)
        if (arr[j] % M[i] != arr[0] % M[i]) break;
    if (j == N) printf("%d ", M[i]);	
}

---

소스코드

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int compare(const void *a, const void *b){
    return *(int*)a - *(int*)b;
}
int M[99], N;
int main(){
    scanf("%d", &N);
    int arr[N];
    for (int i = 0; i < N; i++)
        scanf("%d", &arr[i]);
    qsort(arr, N, sizeof(int), compare);
	
    int x = arr[1]-arr[0], idx = 0;
    int sq = sqrt(x);
    for (int i = 2; i <= sq; i++)
        if (x%i == 0){
            M[idx++] = i;
            if (x/i != i) M[idx++] = x/i;
        }
    qsort(M, idx, sizeof(int), compare);
    M[idx++] = x;
	
    for (int i = 0, j; i < idx; i++){
        for (j = 1; j < N; j++)
            if (arr[j] % M[i] != arr[0] % M[i]) break;
        if (j == N) printf("%d ", M[i]);	
    }
}

---

출처

2981번: 검문