[C++/GCD] 백준 2981 검문

1. 문제

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

2981번: 검문

 

2. 풀이

숫자들이 여러개 입력 될 때

각 숫자는 n = a * x + r(x는 나누는 수, a는 몫, r은 나머지)로 표현 할 수 있다.
A, B, C,.... 이렇게 숫자가 오름차순을 나열 되어있다고 할 때, 각 숫자들은
a * x + r, b * x + r, c * x + r....로 표현 될 수 있고
r = A - a * x = B - b * x
A - B = x * (a - b)
로 근접한 두 수의 차의 약수가 두 수를 나눴을 때 나머지를 모두 같게 하는 수임을 확인 할 수 있다.

 

따라서,

1) 숫자들을 오름차순으로 나열하고
2) 근접한 두 수의 차들의 최대공약수를 구하고
3) 1을 제외한 최대공약수의 약수를 구하면(나누는 수는 1보다 커야한다는 조건)
답을 얻을 수 있다.

 

3. 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
 
// 최대 공약수 구하기
int getGCD(int a, int b){
    return a % b ? getGCD(b, a%b) : b;
}
 
int main() {
    int n;
    cin >> n;
    vector<int> v(n);
 
    // 숫자들 입력
    for(int i = 0; i < n; i++){
        cin >> v[i];
    }
    sort(v.begin(), v.end());
 
    // 앞뒤 숫자 차 간의 gcd를 구함
    int gcd = v[1] - v[0];
    for(int i = 2; i < n; i++){
        gcd = getGCD(gcd, v[i] - v[i - 1]);
    }
 
    // 1을 제외한 gcd의 약수를 구함
    vector<int> divisors;
    divisors.push_back(gcd);
    for(int i = 2; i <= sqrt(gcd); i++){
        if(gcd % i == 0){
            divisors.push_back(i); // 제곱수인 경우
            if(gcd/i != i) divisors.push_back(gcd/i);
        }
    }
    sort(divisors.begin(), divisors.end());
 
    // 결과 출력
    for(int i = 0; i < divisors.size(); i++){
        cout << divisors[i] << " ";
    }
 
    return 0;
}