백준 1684 같은 나머지 c++

문제

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

문제해설

n개의 정수로 된 수열이 존재한다.
모든 수를 같은 수 D로 나누었을 때 모든 수의 나머지가 같아지는 D가 존재한다.
이 D는 여러개 존재할 수 있으며 가장 큰 D를 구하면 된다.

문제풀이

어떤 수 x1이 존재하고 이 수를 D로 나눴을 때의 몫을 p1 나머지를 q라고 하자.
그럼 x1 = Dp1 + q -> q = x1 - Dp1 이라는 식이 생긴다.
다른 수 x2도 D로 나누었을 때 나머지가 같아야하므로
x1 - Dp1 = x2 - Dp2 라고 표현할 수 있다.
x1 - x2 = D(p1 - p2) 로 정리해보면 새로운걸 발견할 수 있다.

x1 - x2는 D의 배수이다. 다르게 표현해보면 D는 (x1-x2)의 약수 중 하나이다.
그렇다면 모든 수들의 차를 구해서 그 차들의 최대공약수를 구하면 될거라고 생각할 수도 있다.
하지만 그럴필요도 없고 그러면 안된다.
수를 정렬시키고 그 수들 사이의 차만 구해서 최대공약수를 구하면 된다.
왜 안되냐면 이 문제에서 음수도 입력으로 들어올 수 있는데
정렬이되지 않은 상태에서 차를 구하면 음수가 나올 수 있기 때문이다.

그리고 모든 수의 차를 구할 필요없이 정렬된 수들의 차이만 구해도 문제가 없다.
직접 구해보면 알 것이다.

결국 입력받은 수들을 정렬시키고 그 수들 사이의 차 n-1개의 최대공약수를 구하면 된다.
n-1개의 최대공약수를 어떻게 구할지 난감할 수도 있는데

1
2
3

int res = tmp[0];
for (int i = 1; i < tmp.size(); i++)
	res = gcd(res, tmp[i]);

이런식으로 두 수 사이의 최대공약수를 다시 입력값으로 넣어서 모든 수를 돌면 구할 수 있다.

전체코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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

int gcd(int x, int y) {
	while (y) {
		int t = x % y;
		x = y;
		y = t;
	}
	return x;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n; cin >> n;
	vector<int>arr(n);
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	sort(arr.begin(), arr.end());

	vector<int>tmp;
	for (int i = 1; i < n; i++)
		tmp.push_back(arr[i] - arr[i - 1]);

	int res = tmp[0];
	for (int i = 1; i < tmp.size(); i++)
		res = gcd(res, tmp[i]);
	cout << res;
	return 0;
}