[BOJ/Gold 4] 백준 2981 검문(C++)

문제 링크

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

2981번: 검문

 

문제

트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다.

상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다.

먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다.

N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오.

입력

첫째 줄에 종이에 적은 수의 개수 N이 주어진다. (2 ≤ N ≤ 100)

다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다. 이 수는 모두 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. 같은 수가 두 번 이상 주어지지 않는다.

항상 M이 하나 이상 존재하는 경우만 입력으로 주어진다.

출력

첫째 줄에 가능한 M을 공백으로 구분하여 모두 출력한다. 이때, M은 증가하는 순서이어야 한다.

예제 입력 1

3
6
34
38

예제 출력 1

2 4

예제 입력 2

5
5
17
23
14
83

예제 출력 2

3

알고리즘 분류

• 수학

풀이

모든 수를 1씩 빼면서 최대공약수를 찾는다면, 최악의 경우 대략 10억 번의 연산을 해야 하므로 1초로는 부족하다.

나머지의 정의를 생각하면, N을 M으로 나눈다고 할 때 나머지는 N에서 N/M을 뺀 값이다. N/M은 순전히 나머지를 생각하지 않고 몫만 계산한 값이기 때문이다. 따라서 수식으로 표현하면

 

이다.

따라서, 배열 A가 있다고 하면, 배열 A에 있는 각각의 수의 나머지는 이렇게 표현할 수 있다.

 

 

A에 있는 모든 수를 M으로 나누었을 때 나머지가 같다고 하였으니, 나머지는 모두 R이라는 같은 수로 표현할 수 있다.

 

이제 위의 식을 서로 빼주면 이렇게 된다.

 

 

따라서, A에 속한 모든 수가 M으로 나눴을 때 나머지가 같다면, 두 수를 뺀 값은 M의 배수라는 것을 알 수 있다.

이제 N개의 수를 오름차순 정렬하고, 인접한 두 수의 차를 구해준다.

그리고 그 차들의 최대공약수를 구해준다. 이 최대공약수가 바로 M이 될 수 있는 값의 최댓값이다.

이제 이 최대공약수의 약수를 모두 구해주면, 그것들이 M이 될 수 있는 모든 값이 된다.

마지막으로 M이 될 수 있는 값들을 오름차순해준 후 공백으로 구분지어 출력해주면 된다.

코드

#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, G;
vector<int> Vec;
vector<int> Sub;
vector<int> Answer;

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 Factors() {
	for (int i = 2; i <= (G / 2); i++) {
		if (G % i == 0) {
			Answer.push_back(i);
		}
	}
}

void Settings() {
	sort(Vec.begin(), Vec.end());
	for (int i = 0; i < ((int)Vec.size() - 1); i++) {
		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) {
		G = Sub[0];
	}
	else {
		G = GCD(Sub[1], Sub[0]);
		for (int i = 2; i < Sub.size(); i++) {
			G = GCD(Sub[i], G);
		}
	}
	Answer.push_back(G);
	Factors();
	sort(Answer.begin(), Answer.end());
}

void Find_Answer() {
	for (int i = 0; i < Answer.size(); i++) {
		if (i == 0) {
			cout << Answer[i];
		}
		else {
			cout << " " << Answer[i];
		}
	}
}

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

	return 0;
}