Baekjoon 17087번 숨바꼭질 6

문제

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

걸린 시간

-

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, s;
    cin >> n >> s;
    vector<int> a(n), d(n);
    for(auto& i : a) cin >> i;
    for(int i = 0; i < n; i++)
        d[i] = abs(s-a[i]);
    if(n == 1){
        cout << d[0] << "\n";
        return 0;
    }
    int ans = gcd(d[0], d[1]);
    for(int i = 2; i < n; i++)
        ans = gcd(ans, d[i]);
    cout << ans << "\n";
    return 0;
}

정수론 연습 문제이다. 정수론 기초 개념에 근거해서 솔루션을 찾았다.

3개 이상의 수에 대한 최대공약수는 두개씩 묶어 게산한 결과와 같다.