[BOJ/Gold 5] 백준 1684 같은 나머지(C++)

문제 링크

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

1684번: 같은 나머지

 

문제

정수 N을 정수 D로 나눴을 때의 몫을 Q, 나머지를 R이라고 하면 항등식 R = N - Q×D가 성립한다.

n개의 정수로 된 수열이 있을 때, 모든 정수를 한 정수 D로 나눴을 때 나머지가 같아지는 경우가 있다. 그리고 수열에 따라서는 이러한 정수 D가 여러 개 존재할 수 있다.

n개의 정수로 된 수열이 주어졌을 때, 가장 큰 D를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1≤n≤1,000)이 주어진다. 다음 줄에는 절댓값이 1,000,000을 넘지 않는 n개의 정수들이 주어진다.

출력

첫째 줄에 가장 큰 D를 출력한다. 항상 가장 큰 D가 존재하는 경우만 입력으로 주어진다.

예제 입력 1

4
701 1059 1417 2312

예제 출력 1

179

예제 입력 2

5
14 23 17 32 122

예제 출력 2

3

예제 입력 3

5
14 -22 17 -31 -124

예제 출력 3

3

알고리즘 분류

• 수학

풀이

이 문제랑 거의 동일하다.

17433번: 신비로운 수

항상 가장 큰 D가 존재하는 경우만 입력으로 주어진다고 하였으므로, D가 0이 나오는 경우는 없을 것이다.

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);

using namespace std;
int N, D;
vector<int> Vec;
vector<int> Sub;

int GCD(int N, int M) {
	while (1) {
		int R = N % M;
		if (R == 0) {
			return M;
		}
		N = M;
		M = R;
	};
}

void Input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int I;
		cin >> I;
		Vec.push_back(I);
	}
}

void Settings() {
	sort(Vec.begin(), Vec.end());
	if (Vec.size() > 1) {
		for (int i = 0; i < ((int)Vec.size() - 1); i++) {
			if (Vec[i + 1] - Vec[i] > 0) {
				Sub.push_back(Vec[i + 1] - Vec[i]);
			}
		}
	}
	sort(Sub.begin(), Sub.end());
	Sub.erase(unique(Sub.begin(), Sub.end()), Sub.end());
	if (Sub.size() == 1) {
		D = Sub[0];
	}
	else if (Sub.size() > 1) {
		D = GCD(Sub[1], Sub[0]);
		for (int i = 2; i < Sub.size(); i++) {
			D = GCD(Sub[i], D);
		}
	}
}

void Find_Answer() {
	cout << D << "\n";
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}