같은 나머지 (feat. 백준, 1684번)

같은 나머지
https://www.acmicpc.net/problem/1684

1684번: 같은 나머지

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
inline int gcd(register int a, register int b) {
	return a % b ? gcd(b, a % b) : b;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N, arr[1000];
	cin >> N;
	for (register int n = 0; n < N; ++n) {
		cin >> arr[n];
	}
	sort(arr, arr + N);
	for (register int i = 1; i < N; ++i)
		arr[i - 1] = arr[i] - arr[i - 1];
	set<int> tmp;
	for (register int i = 1; i < N - 1; ++i)
		if (arr[i] != 0)
			tmp.insert(gcd(arr[0], arr[i]));
	cout << *tmp.begin();
	return 0;
}
// *&)*@*

 

1. r1 = n1 - q1 * D
   r2 = n2 - q2 * D = n1 - q1 * D (나머지 r1, r2가 같기 때문)
   n2 - n1 = (q2 - q1) * D
2. 따라서 (n2 - n1)는 D의 배수이며, D는 (n2 - n1)의 약수입니다.
3. 따라서 입력된 값을 N1, N2, N3, N4 라고 할때 N2 - N1, N3 - N2, N4 - N3 은 동일한 약수를 갖습니다.