[Algorithm]Baekjoon 2981번 : 검문

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
#include <climits>
#include <bitset>
#include <cmath>
 
using namespace std;
 
int n;
int arr[101] = { 0 };
 
 
int GetGCD(int a, int b)
{
    int maxNum = max(a, b);
    int minNum = min(a, b);
 
    while (maxNum % minNum != 0)
    {
        int temp = maxNum % minNum;
        maxNum = minNum;
        minNum = temp;
    }
 
    return minNum;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
    }
 
    sort(arr, arr + n);
 
    int gcd = arr[1] - arr[0];
 
    for (int i = 2; i < n; ++i)
    {
        gcd = GetGCD(gcd, arr[i] - arr[i-1]);
    }
 
    vector<int> result;
 
    for (int i = 2; i * i <= gcd; ++i)
    {
        if (gcd % i == 0)
        {
            result.push_back(i);
            result.push_back(gcd / i);
        }
    }
 
    result.push_back(gcd);
    sort(result.begin(), result.end());
    result.erase(unique(result.begin(), result.end()), result.end());
 
    for (int i = 0; i < result.size(); ++i)
    {
        printf("%d ", result[i]);
    }
}
 
 

 

 

많이 어려웠던 정수론 문제. 당연히? 자력으론 못 풀었다.

자세한 그림까지 첨부된 설명은 다른 분들의 글을 참고... 그정도까지 친절하게 설명할 여력이 없다..

 

최대한 간단하게 설명하면, 문제에서 주어지는 숫자들을 똑같은 M이라는 숫자로 나누면 전부다 R이라는 똑같은 나머지값이 나와야 한다. (M은 여러개다)

일단 이 점을 인지.

 

그리고 이 식을 이해해야 한다.

특정 수 A가 있다고 가정한다.

이 때, 이 A를 몫(M)과 나머지(R)로 정리하면 아래와 같다.

 

A = (A / M) * M + R

 

여기서 1차적인 의문이 들 수 있다. A/M * M이면, 그냥 A아닌가?????

 

그러나 여기서 괄호의 A / M 은, 그냥 몫만 취하는 부분이다.

예를들어 A가 5고 M이 3이면, 괄호의 A/M은 1이 된다. 정확히 5/3이 아니란 것. 몫인 1만 가져간다.

 

저 식을 R을 기준으로 다시 바꾸면

 

R = A - (A/M) * M 이 된다.

여기서 A는 각각의 숫자를 의미한다.

입력받은 배열의 인덱스 0,1을 기준으로 하면 다음과 같다.

 

R = A0 - (A0 / M ) * M

R = A1 - (A1 / M) * M

 

우리는 M을 기준으로 하는 어떤 식을 구해보고 싶다.

그러기 위해 미지수는 최대한 줄여주는게 좋으니, R값을 없애기 위해 아래식(A1)에서 위 식(A0) 을 빼보자.

 

그러면 

0 = A1 - (A1 / M) * M - A0 + (A0 / M) * M

A1 - A0 = (A1 / M) * M - (A0 / M) * M

A1 - A0 = M * (A1 / M - A0 /M)

 

이 된다.

 

즉, A1 에서 A0를 빼면 M의 배수가 나온다는게 확실해진다는 것.

그렇기 때문에 이렇게 인접한 수의 차이를 모두 구한다.

그렇게 구한 숫자들은, M의 배수가 된다는 것이다.

 

우리는 이 때, 각 숫자들의 최대공약수를 구하면 된다. 

최대공약수는 공통된 약수들 중의 최대값, 즉 각 숫자들의 인수들 중에 최대값을 의미한다.

우리가 구하려는 M의 성질과 일치한다는 것이다.

최대공약수를 구한다면, 이 최대공약수의 약수들 또한 M값에 일치하기때문에 구해줘야 한다.

 

최대공약수를 구할때는 유명한 방법인 유클리드호제법을 이용한다.

입력으로 주어지는 숫자값은 최대 10억이니.. 무식하게 1부터 일일이 하는것은 당연히 안된다.

 

최대공약수를 구한 후, 약수의 개수구하는것도 센스있게 i * i <= gcd 로, 불필요한 반복문을 줄여주도록 한다.

약수에 해당하는것을 answer에 push_back할 때, gcd / i값도 당연히 추가로 넣지만 중복된 값이 들어갈 수 있기 때문에

vector의 멤버함수인 erase와 std함수인 unique를 통해 중복된 값을 전부 없애준다.