[C/C++] 백준 - 2981번 : 검문

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은 증가하는 순서이어야 한다.

 

이 문제를 처음 분석할 때 입력되는 각 수들의 최대공약수를 구하고, 그 최대공약수를 더하거나 뺀 2개의 수 중 나머지가 같은 값이 존재할 것이라고 생각했다. 그래서 그렇게 코드를 짜보았는데 최대공약수가 1이 나오는 모든 경우가 반례가 될 수 있기 때문에 다른 방법이 있다고 생각했다.

그러면 어떻게 구해야 나머지가 모두 같은 수를 찾을 수 있을까 생각해봤다..

때려맞추는 문제를 낼리는 없고, 수학적 접근이 필요하다고 생각했고, 각 수들의 차이를 저장하는 배열을 생성하고,

그 배열에서의 최대공약수를 구해보자고 생각했다. 이때까지는 그냥 해보자라는 생각으로 해봤고 최대공약수를 구하고보니 그 최대공약수의 약수가 답이 된다는 것을 알 수 있었다.

 

왜 그런지는 몰랐기에, 구글링을 좀 해봤고 다른 분의 증명을 보고 알 수 있었다.

v[i] = temp[i] * m + r

로 배열을 나타낼 수 있다. m은 각 배열의 최대공약수가 되는 것이고, r은 나머지가 되는것이다

여기서 r을 없애게 되면 나머지는 모두 0으로 같게 되는 것이 이 문제가 묻는 것이므로

v[i] - v[i-1] = (temp[i] - temp[i-1]) * m + (r-r)

로 r을 없애는 것이다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>

using namespace std;

int N;
int ramda[101];
int delta[101];

int gcd(int x, int y) {
	if (y == 0) return x;
	return gcd(y, x % y);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N;
	for (int i = 0; i < N; i++) cin >> ramda[i];
	sort(ramda, ramda + N);
	for (int i = 0; i < N - 1; i++) {
		delta[i] = ramda[i + 1] - ramda[i];
	}

	int x = gcd(delta[0], delta[1]);
	for (int i = 2; i < N - 1; i++) {
		x = gcd(x, delta[i]);
	}

	vector<int> Answer;
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0) {
			Answer.push_back(i);
			if(x/i != i)
				Answer.push_back(x / i);
		}
	}
	Answer.push_back(x);
	sort(Answer.begin(), Answer.end());

	for (int i = 0; i < Answer.size(); i++) cout << Answer[i] << " ";
	
	return 0;
}