[수학 3 단계] 백준 2981번 검문

문제

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

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

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

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

입력

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

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

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

출력

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

A[1] % M = A[1] - (A[1] / M) * M

A[2] % M = A[2] - (A[2] / M) * M

A[3] % M = A[3] - (A[3] / M ) * M

이로부터 

A[1] % M= A[2] % M= A[3] % M 이기 때문에

A[1] - A[2] = M * (A[1] / M  -  A[2] / M) 

A[2] - A[3] = M * (A[2] / M  -  A[3] / M) 

A[3] - A[4] = M * (A[3] / M  -  A[4] / M) 

 

A[N-1] - A[N] = M * (A[N-1] / M - A[N] / M ) 성립

즉 A[k-1] - A[k] 들은 모두 같은 약수를 가지고 있다는 말이다.

 

따라서 이들의 최대 공약수를 구하고 그 최대 공약수의 약수들이 M이 될 수 있는 수이므로 약수를 구하면된다.

 

이때 약수를 구하는 방법을 1부터 M까지 나눴을 때 나머지가 0인것으로 구하면 시간초과가 발생하는데,

i * i <= M일 때

i와 gcd/i를 함께 저장하는 방식으로 검색 시간을 반으로 줄일 수 있다.

 

12의 약수

1 2 3 4 6 12 의 경우 왼쪽 반의 원소는 제곱을 해도 12를 넘지 않는다.

따라서 왼쪽에 대해서만 조사를 해서 같이 넣는데 주의할 점은 중복이 들어가면 안된다.

 

36의 약수

1 2 3 4 6 9 12 18 36 의 경우

무조건 i와 gcd/i를 함께 넣으면 6이 두번들어감. 따라서 같지 않을 때 gcd/i를 추가로 넣어주게 하면 된다.

그리고 2와 18이 들어가고 3과 12가 들어가므로 3이 18보다 늦게 저장됨

따라서 정렬 필수.

#include <iostream>
#include <vector>
#include<queue>
#include <string>
#include<cmath>
#include<string.h>
#include <map>
#include<algorithm>
using namespace std;
int arr[100];

int gcd(int a, int b)
{
	int c;
	while (b)
	{
		c = a % b;
		a = b;
		b = c;
	}
	return a;
}
int main() {

	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	sort(arr, arr + N);

	int max_gcd = arr[1] - arr[0];
	for (int i = 2; i < N; i++)
	{
		max_gcd = gcd(max_gcd, arr[i] - arr[i - 1]);
	}
	
	vector<int> vec;
	for (int i = 1; i * i <= max_gcd; i++)
	{
		if (max_gcd % i == 0)
		{
			vec.push_back(i);
			if (i != max_gcd / i)
			{
				vec.push_back(max_gcd / i);
			}
		}
	}
	sort(vec.begin(), vec.end());
	for (int i = 0; i < vec.size(); i++)
	{
		if (vec[i] == 1)
		{
			continue;
		}
		cout << vec[i] << " ";
	}

}