[BOJ] 2981: 검문

문제 소개

2020.03.27 기준,  solved.ac 실버 1티어 문제입니다.

 

문제 번호가 낮고 예전에 만들어진 문제여서 많은 분들이 풀이를 올리신 것 같지만 끄적여봅니다.

먼저, 문제를 풀 수 있는 아이디어부터 설명하고

코드를 설명하겠습니다.

 

 

문제 링크

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

2981번: 검문

아이디어

대충이라도 문제를 들여다보면, 아 최대공약수를 활용하면 될 것 같은데 라고 생각이듭니다.

맞습니다. 바로 최대 공약수 문제입니다.

근데, 중요한 것은 어떤 수들의 최대 공약수를 구해야하지? 를 아는 것입니다.

 

한번 문제의 조건들을 식으로 나타내봅시다.

 

a_0 % M = k

a_1 % M = k

a_2 % M = k

...

 

(k는 임의의 나머지)

다르게 표현해볼까요?

 

a_0 = c_0 * M + k

a_1 = c_1 * M + k

a_2 = c_2 * M + k

...

(k는 임의의 나머지, c_i는 임의의 자연수입니다.)

 

어? 저 식은 너무 미지수가 많은데, k는 식들을 서로 빼주면 사라질 것 같네요?

(a_0 < a_1 < ... < a_(n-1)을 가정하고 해봅시다.)

 

a_1 - a_0 = (c_1 - c_0) *M

a_2 - a_1 = (c_2 - c_1) * M

a_2 - a_0 = (c_2 - c_0) *M

..

 

이 식을 자세히 들여다보면 다음 사실을 알게됩니다.

 

만약에 좌항의 뺄셈 결과가 양수인 것들을 모조리 나열하고 나서, 이 수들의 최대 공약수를 구하면 이 문제에서 나올 수 있는 답 중 최대값일 것이다.

 

그러면 나머지 답은 무엇일까요? 바로 이 최대공약수의 1을 제외한 약수입니다.

 

이제, 한번 코드로 바꾸어봅시다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N;
int ar[110];
vector<int> V;
vector<int> ans;
int G;

int gcd(int a,int b) {
    return b>0?gcd(b,a%b):a;
}

int main() {
    cin >> N;
    for(int x = 0; x < N; x++) cin >> ar[x];
    sort(ar,ar+N);
    for(int x = 0; x < N; x++) {
        for(int y = 1; y < N; y++) {
            V.push_back(ar[y] - ar[x]);
        }
    }
    G = V[0];
    for(auto i : V) {
        G = gcd(G,i);
    }
    ans = {G};

    for(int x=2; x*x <= G; x++) {
        if(G % x == 0) {
            ans.push_back(x);
            if(G != x*x) {
                ans.push_back(G/x);
            }
        }
    }
    sort(ans.begin(),ans.end());
    for(auto i:ans) {
        cout << i << " ";   
    }

}

Rmx