[백준] 2981번 : 검문

문제

 

---

본문

 

입력 A, B, C가 있다고 하자. 이 수들을 M으로 나눴을 때의 나머지가 전부 같으니 이를 r이라고 하자.

그리고 입력된 수를 M으로 나눴을 때의 몫을 각각 x, y, z라고 하자. 별로 중요하진 않은 애들이다.

 

정리하면

A = M*x + r

B = M*y + r

C = M*z + r

이 된다.

 

여기서 A-B와 B-C를 해보겠다.

A-B = M(w-x)

B-C = M(x-y)

편의상 (w-x)를 k로 (x-y)를 l로 놓으면

A-B = Mk, B-C = Ml이 된다.

 

그니까 M은 (A-B)와 (B-C)의 공약수라는 것이다. 이걸 일반화하면

N개의 숫자가 있는 집합 X로 만들 수 있는 모든 K(K=A-B, A∈B∈X, A≠B)의 공약수가 M이 된다는 것이다.

쉽게 풀어쓰면 집합 X에서 숫자 2개 뽑아서 걔네 둘 빼서 만든 모든 수의 공약수가 M이란 것이다.

 

공약수는 어떻게 구할까? 최대공약수의 약수가 공약수다.

---

소스코드

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

long long num_arr[100];
vector<int> v;

int gcd(int a, int b) { //유클리드 호제법
    int temp, n;

    if (a < b) {
        temp = a;
        a = b;
        b = temp;
    }
    while (b != 0) {
        n = a % b;
        a = b;
        b = n;
    }
    return a;
}

void findM(int N) { //제일 앞에 두개 빼고(초기값) 그 뒤부터 인접한 애들끼리 빼서 최대공약수 구하기
    long long g = num_arr[1] - num_arr[0];

    for (int i = 2; i < N; i++)
        g = gcd(g, num_arr[i] - num_arr[i - 1]);
    for (int i = 2; i * i <= g; i++) { //약수를 구하는 빠른 방법
        if (g % i == 0) {
            v.push_back(i);
            v.push_back(g / i);
        }
    }
    v.push_back(g);
}

int main() { //수학적 지식 필요
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    int N;

    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> num_arr[i];
    sort(num_arr, num_arr + N);
    findM(N);
    sort(v.begin(), v.end()); //정렬
    v.erase(unique(v.begin(), v.end()), v.end()); //중복제거(정렬하고 해야한다고 함)
    for (int i = 0; i < v.size(); i++)
        cout << v[i] << ' ';
}

전체 소스코드다.

 

void findM(int N) { //제일 앞에 두개 빼고(초기값) 그 뒤부터 인접한 애들끼리 빼서 최대공약수 구하기
    long long g = num_arr[1] - num_arr[0];

    for (int i = 2; i < N; i++)
        g = gcd(g, num_arr[i] - num_arr[i - 1]);
    for (int i = 2; i * i <= g; i++) { //약수를 구하는 빠른 방법
        if (g % i == 0) {
            v.push_back(i);
            v.push_back(g / i);
        }
    }
    v.push_back(g);
}

findM 함수에서는 가능한 M을 전부 찾는다.

가능한 모든 수의 조합을 뽑아서 계산하는 것보다는 연쇄적으로 최대공약수를 구해나가는게 더 빠를 것이다.

 

그니까

A-B와 B-C의 최대공약수(g)를 구하고 g와 C-D의 최대공약수를 구하고...하는 식으로 구한다는 뜻이다.

main에서 숫자 배열을 오름차순 정렬했기 때문에 음수가 나올 일은 없다.

 

그렇게 구한 최종적인 최대공약수 g의 약수를 구해 배열 v에 넣어준다.

 

int gcd(int a, int b) { //유클리드 호제법
    int temp, n;

    if (a < b) {
        temp = a;
        a = b;
        b = temp;
    }
    while (b != 0) {
        n = a % b;
        a = b;
        b = n;
    }
    return a;
}

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

 

    sort(v.begin(), v.end()); //정렬
    v.erase(unique(v.begin(), v.end()), v.end()); //중복제거(정렬하고 해야한다고 함)
    for (int i = 0; i < v.size(); i++)
        cout << v[i] << ' ';

findM 함수로 구한 M이 들어있는 배열 v에는 중복된 값이 있을 수 있으므로 main에서 중복을 제거한 뒤 출력한다.