백준 2981번 검문

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

2981번: 검문

풀이

N개의 수 중 i번째 수를 $a_i$라고, 구하고자 하는 값을 $M$이라고 하겠습니다.

N개의 수는 $M$으로 나눈 나머지가 모두 같아야 하므로 이때의 나머지를 $k$라고 하면

$1\leq i\leq N$인 모든 $i$에 대해 $a_i - k$는 $M$의 배수입니다. 

따라서 N개의 수 중 어떤 두 수를 잡더라도 두 수의 차는 $M$의 배수가 됩니다.

즉, $1\leq i, j\leq N$인 모든 $i, j$에 대해 $|a_i - a_j|$는 $M$의 배수입니다. 

이때 가능한 $M$은 모든 인접한 두 수들의 차의 공약수이며,

$M$의 최댓값은 모든 인접한 두 수들의 차의 최대공약수가 됩니다.

식으로 나타내면 $M$의 최댓값 = $\gcd(|a_1 - a_2|, |a_2 - a_3|, ... , |a_{n-1}, a_n|)$이 됩니다.

이렇게 구한 $M$의 최댓값의 약수를 구하면 가능한 $M$의 값을 모두 구할 수 있습니다.

 

코드

유클리드 호제법을 이용하여 인접한 두 수들의 최대공약수를 구했습니다.

M의 최댓값의 약수를 효과적으로 구하기 위해 $\sqrt{M}$번만 루프를 돌았고, 크기순으로 출력하기 위해 루프 안에서 발견되는 약수 중 $\sqrt{M}$ 이상인 수들은 스택에 넣었습니다.

 

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <stack>
using namespace std;
int gcd(int a, int b) {
    if (a % b)
        return gcd(b, a % b);
    else
        return b;
}
stack<int> stk;
int main() {
    int n, got, last = 0, nowgcd = 0;
    scanf("%d", &n);
    while (n--) {
        scanf("%d", &got);
        if (nowgcd)
            nowgcd = gcd(abs(last - got), nowgcd);
        else if (last)
            nowgcd = abs(last - got);
        last = got;
    }
    stk.push(nowgcd);
    for (int i = 2; i * i <= nowgcd; i++) {
        if (!(nowgcd % i)) {
            printf("%d ", i);
            if (i * i != nowgcd)
                stk.push(nowgcd / i);
        }
    }
    while (!stk.empty()) {
        got = stk.top();
        stk.pop();
        printf("%d ", got);
    }
    return 0;
}

 

사족

글 쓸 때 처음으로 LaTeX 사용해봤어요

재밌다!!!