[백준][C++] 17087: 숨바꼭질 6

문제 링크: https://www.acmicpc.net/problem/17087

 

수빈이를 좌표 0에 놓고, 동생들을 -S만큼 이동시켜보면 '아 최대공약수 문제구나!' 라는걸 아실 수 있을 겁니다. 최대공약수의 기초 정보는 저번 게시물을 참고해주세요.

 

동생과 수빈의 거리차이를 모두 구한 뒤, 이 거리 차이들의 최대공약수를 구하면 됩니다.

\[GCD(|A_1 - S|, |A_2 - S|, \ldots , |A_N - S|)\]

식으로 표현하면 위와 같이 나옵니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);


	int n, s;
	cin >> n >> s;
	vector<int> diff;
	diff.resize(n);
	for (auto& c : diff) {
		cin >> c;
		c = abs(s-c);
	}

	int ans = diff[0];
	for (int i = 1; i < n; ++i) {
		ans = gcd(ans, diff[i]);
	}

	cout << ans;

	return 0;
}

세 수 이상의 최대공약수를 구할때는 \(GCD(GCD(a,b),c)\)와 같은 형태로 연속적으로 gcd 함수를 사용하면 됩니다.