[알고리즘] 백준 2981 - 검문 (C++)

[문제 링크] : https://www.acmicpc.net/problem/2981

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

int N, T;
int inp;
vector<int> V, Ans;

int solve(int a, int b){
    if(b == 0){
        return a;
    }
    return solve(b, a % b);
}

int main() {
    cin >> N;
    for(int i=0; i<N; i++){	
        cin >> inp;
        V.push_back(inp);
    }
    sort(V.begin(), V.end());

    T = V[1] - V[0];
    for(int i=2; i<N; i++){
        T = solve(T, V[i] - V[i - 1]);
    }

    for(int i=2; i*i<=T; i++){ 
        if(T % i == 0){
            Ans.push_back(i); 
            Ans.push_back(T / i);
        }
    }

    Ans.push_back(T);

    sort(Ans.begin(), Ans.end());
    Ans.erase(unique(Ans.begin(), Ans.end()), Ans.end());

    for(int i=0; i<Ans.size(); i++){
        cout << Ans[i] << " ";
    }
    cout << "\n";
    
    return 0;
}