[ 백준 ] 2981 / 검문

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
83/228
post-thumbnail

# Appreciation

/*
 * Problem :: 2981 / 검문
 *
 * Kind :: Math
 *
 * Insight
 * - x1, x2, ..., xn_1, xn
 *   x1%M = x2%M = ... = xn_1%M = xn%M
 *   + abs(x1-x2)%M = 0
 *     abs(x1-x3)%M = 0
 *     abs(x1-x4)%M = 0
 *     ...
 *     abs(xn-xn_2)%M = 0
 *     abs(xn-xn_1)%M = 0
 *     # abs(x1-x2), ..., abs(xn-xn_1) 은 모두 M의 배수
 *       max(M) 은 abs(x1-x2), ..., abs(xn-xn_1) 의 최대 공약수
 *       가능한 M 들은 max(M) 의 약수들
 *
 * Point
 * - 차이를 abs 로 구하는건 귀찮으니
 *   오름차순으로 정렬해버리자
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

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

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
int gcd(int a, int b);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N; cin >> N;
    int A[N];
    for (int i=0; i<N; i++)
        cin >> A[i];

    // Process
    sort(A, A+N);
    int M = A[1]-A[0]; /* max(M) */
    for (int i=0; i<N; i++) {
        for (int j=i+1; j<N; j++) {
            M = gcd(M, A[j]-A[i]);
        }
    }

    set<int> D; /* max(M) 의 약수들 */
    for (int i=1; i*i<=M; i++) {
        if (M%i == 0) {
            D.insert(i);
            D.insert(M/i);
        }
    } D.erase(1); /* 1은 제외 */

    // Control : Output
    for (int d : D) {
        cout << d << ' ';
    } cout << endl;
}

// Helper Functions
int gcd(int a, int b)
/* 유클리드 호제법으로 최대공약수 구하기 */
/* gcd(a, b) = gcd(b, a%b) */
{
    int r;
    while (b) {
        r = a % b;
        a = b;
        b = r;
    } return a;
}
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글