#2981

• 문제

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

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

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

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

• 코드

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

using namespace std;

//최대 공약수 구하는 함수
int gcdIter(int a, int b) {
	while (b) {
		a %= b;
		swap(a, b);
	}
	return a;
}


set<int> cal(vector<int>& v, int n) {
	int num; // 최대공약수 구할 기준 수
	set<int> s; //결과를 구할 셋

	//이웃한 수들간의 차끼리 최대공약수 구하기
	num = v[1] - v[0];

	for (int i = 2; i < n; i++) {
		num = gcdIter(num, v[i] - v[i - 1]);
	}

	//최대공약수의 약수 구하기
	for (int i = 2; i*i <= num; i++) { //시간 초과 해결 
		if (num % i == 0) {
			s.insert(i);
			s.insert(num/i);
		}
	}
	s.insert(num); //최대 공약수까지 넣기 
	
	return s;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;
	set<int> result; //결과를 저장할 셋

	//입력 
	cin >> n;

	vector<int> v;

	for (int i = 0; i < n; i++) {
		cin >> m;
		v.push_back(m);
	}

	//연산
	//차를 쉽게 구하기 위해 정렬
	sort(v.begin(), v.end());
	result = cal(v, n);

	//출력
	for (auto iter : result) {
		cout << iter << " ";
	}
	
	return 0;
}

• 해설

1. gcdIter 함수

- 최대 공약수를 구하는 함수

 

2. cal 함수

- 나머지가 모두 같게되는 m 계산하는 함수

: 이웃한 수들간의 차끼리 최대공약수를 구한 후 최대공약수의 약수를 구하면 m을 구할 수 있음

: gcdIter함수를 통해 계속해서 이웃한 수들간의 차끼리 최대공약수를 구함

: 최대공약수의 약수를 구할 때 i와 num/i를 한 번에 insert하여 i*i <=num까지만 연산을 하도록 함

: 마지막 본인까지 최대공약수에 넣은 후 set를 반환

 

3. main 함수

: 모두 입력 받아 벡터에 저장한 후, 계산하기 쉽게 정렬한 뒤 cal함수를 통해 연산