[백준][C++] 2981: 검문

문제

2981번: 검문

풀이

유클리드 호제법, 수학

 

완전 탐색으로 하면 시간초과가 발생한다. 주어진 정수 A를 M으로 나눈 나머지가 R이라면 다음을 만족한다.

R = A - (A / M) * M

여기서 A는 배열로 주이지므로 다음이 만족한다.

R = A[0] - (A[0] / M) * M

R = A[1] - (A[1] / M) * M

...

R = A[N - 1] - (A[N - 1] / M) * M

 

문제에서 R이 같은 값이므로 다음이 만족한다.

A[1] - A[0] = (A[1] / M - A[0] / M) * M

그러므로 R이 같은 값을 만족하려면 인접한 수의 차이가 M의 배수여야 한다.

 

즉, 인접한 수의 차이들의 최대공약수가 M의 최댓값이 되며, M의 약수로 나눠도 답이 성립하므로, 문제의 정답은 인접한 수의 차이의 최대공약수와 최대공약수의 약수가 된다(1은 제외).

코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> nums;
vector<int> answer;

int gcd(int a, int b)
{
    if (a < b)
    {
        swap(a, b);
    }

    int temp;
    while (b != 0)
    {
        temp = a % b;
        a = b;
        b = temp;
    }

    return a;
}

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

    int N;
    cin >> N;

    for (int i = 0; i < N; ++i)
    {
        int temp;
        cin >> temp;
        nums.push_back(temp);
    }
    sort(nums.begin(), nums.end());

    // 인접한 두 수의 차의 최대공약수를 구한다.
    int GCD = nums[1] - nums[0];
    for (int i = 2; i < N; ++i)
    {
        GCD = gcd(GCD, nums[i] - nums[i - 1]);
    }

    // 최대공약수의 약수를 구한다.
    for (int i = 2; i * i <= GCD; ++i)
    {
        if (GCD % i == 0)
        {
            answer.push_back(i);
            if (i != GCD / i)
            {
                answer.push_back(GCD / i);
            }
        }
    }
    answer.push_back(GCD);

    sort(answer.begin(), answer.end());

    for (int i = 0; i < answer.size(); ++i)
    {
        cout << answer[i] << " ";
    }

    return 0;
}