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

 

 

 

유클리드를 O(n)만큼 시도해야 한다는 것에 주의.

 

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

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

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);

	int N, S;

	cin >> N >> S;

	vector<int> v;

	if (N == 1)
	{
		int input;
		cin >> input;

		cout << abs(input - S);

		return 0;
	}
	else
	{


		for (int i = 0; i < N; i++)
		{
			int input;
			cin >> input;
			v.push_back(abs(input - S));
		}

		sort(v.begin(), v.end());

		int tmp = v[0];

		for (int i = 1; i < N; i++)
		{
			tmp = Euclid(tmp, v[i]);

		}


	
		cout << tmp;
		
			
	}
	return 0;
}