백준 2981 검문 (C++)

2981번: 검문

수학적 공식을 이용한 문제이다. 문제에서 주어지는 값들의 나머지가 모두 같은 값들을 찾아야 한다. 즉 아래의 식으로 나타낼 수 있다.

- A[1] % M = A[1] - (A[1] / M) * M
- A[2] % M = A[2] - (A[2] / M) * M
- :
- A[N] % M = A[N] - (A[N] / M) * M

나머지가 같으므로 A[1] % M = A[2] % M 이므로, 즉 A[1] - (A[1] / M) * M = A[2] - (A[2] / M) * M을 성립한다. 이를 정리하면 아래와 같다.

- A[2] - A[1] = (A[2] / M - A[1] / M) * M
- A[3] - A[2] = (A[3] / M - A[2] / M) * M
- :
- A[N] - A[N - 1] = (A[N] / M - A[N - 1] / M) * M

이를 통해 알 수 있는 것은 어느 값에서 다른 값을 뺄 경우 공통된 M을 가지고 있다는 것이다. 그렇기에 공통된 M을 찾기 위해 각 차이값 간의 최대 공약수를 구해주고 이 값의 약수를 출력해주면 된다. 최대공약수를 구하는 방식은 유클리드 호제법을 사용하여 구해주었고 약수를 구할 때는 중복값을 없애기 위해 set을 이용해주었다. 그 후 약수들을 출력해주었다.
어려웠던 문제였다. 먼가 어렴풋이 최대공약수를 활용할 것 같은 느낌에 이것저것 시도를 해봤지만 실패를 했고 블로그를 참고하여 문제를 해결하였다. 역시 이러한 문제는 수학적으로 접근을 해야지 풀 수 있는것 같다. 수학적으로 접근을 해봐야 한다는 점도 인지해두자.

---

#include <iostream>
#include <algorithm>
#include <cmath>
#include <set>

using namespace std;

int N, min_a = 1e9;
int A[100];
set<int> result;

int findGcd(int a, int b) {
    return a % b == 0 ? b : findGcd(b, a % b);
}

void solution() {
    sort(A, A + N);

    int gcd = A[1] - A[0];

    for (int i = 2; i < N; i++) {
        gcd = findGcd(gcd, A[i] - A[i - 1]);
    }

    for (int i = 2; i <= sqrt(gcd); i++) {
        if (gcd % i != 0) continue;
        result.insert(i);
        result.insert(gcd / i);
    }
    result.insert(gcd);

    for (auto elem : result) {
        cout << elem << " ";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> A[i];

        min_a = min(min_a, A[i]);
    }

    solution();

    return 0;
}