[BOJ] 2981 - GRANICA

문제 : https://www.acmicpc.net/problem/2981

---

[수학지식]

수학적인 지식이 정말 많이 쓰인 문제입니다.

차근차근 정리해보도록 하겠습니다.

 

K개의 자연수가 있다고 하자. ( 1 ≤ k ≤ 100 )

이때, M으로 나눈 나머지가 t로 모두 같다고 하면 다음과 같은 식이 성립한다.

[정리1]

이 식을 이용해 다음과 같은 정리를 얻을 수 있습니다.

 

[정리2]

임의의 i, j 에 대해

[정리3]

즉, 두 개의 숫자의 차이는 M으로 나눠짐을 알 수 있습니다.

[최종정리]

M으로 모든 숫자들을 나누었을 때, 나머지가 같다면 정리 2,3에 의해 M은 임의의 두 수의 차이의 약수가 됩니다.

즉, M은 두 숫자의 차이 값들의 공약수가 됩니다.

따라서, 모든 숫자들의 차이에 대해서 최대공약수를 구하고,  최대공약수의 약수를 출력해주면 되는 문제입니다.

 

[+추가정리]

수학과 정수론 시간에 배우는 정리로, 증명은 너무 간단하니 생략하겠습니다.

위의 정리를 이용하면 다음과 같은 연산 낭비를 막을 수 있습니다.

예를 들어 N1, N2, N3, N4 ( N1 < N2 < N3 < N4 ) 수가 주어졌을 때, 가능한 모든 차이는

N4 - N3 / N4 - N2 / N4 - N1 / N3 - N2 / N3 - N1 / N2 - N1 이 됩니다.

그리고 우리는 이 6개의 값에 대해서 GCD(최대공약수)를 구해야 됩니다.

하지만 위의 정리를 이용하면, 

N4 - N3 / N3 - N2 / N2 - N1 의 최대공약수만 구해도 됩니다.

 

[알고리즘풀이]

1. 입력된 숫자들을 크기에 따라 정렬해준다.

2. 입력된 숫자들의 모든 차이에 대해서 최대 공약수(g)를 구해준다.

3. 그 최대공약수의 약수(g)들을 출력해준다.

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

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

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;
	vector<int> v;
	for (int i = 0; i < n; i++) {
		int temp;
		cin >> temp;
		v.push_back(temp);
	}
	sort(v.begin(), v.end());

	int g = gcd(v[1] - v[0], v[1] - v[0]);

	for (int i = 1; i < n - 1; i++) {
		g = gcd(g, v[i + 1] - v[i]);
	}
	vector<int> vv;

	for (int i = 1; i * i <= g; i++) {
		if (g % i == 0) {
			if (i == 1) vv.push_back(g);
			else if (i * i == g)
				vv.push_back(i);
			else{
				vv.push_back(i);
				vv.push_back(g / i);
			}
		}
	}

	sort(vv.begin(),vv.end());
	for (int i = 0; i < vv.size(); i++)
		cout << vv[i] << ' ';
}

---