[C++] 백준 2981 검문

#include <iostream>
#include <vector>
#include <algorithm>
 
int arr[101] = {};
int answer[101] = {};
 
int gcd(int a, int b)
{
	if (b == 0)
	{
		return a;
	}
 
	return gcd(b, a % b);
}
 
int main()
{
	int N = 0;
	std::cin >> N;
 
	for (int i = 0; i < N; ++i)
	{
		std::cin >> arr[i];
	}
 
	std::sort(arr, arr + N);
 
	int remainder = arr[1] - arr[0];
 
	for (int i = 2; i < N; ++i)
	{
		remainder = gcd(remainder, arr[i] - arr[i - 1]);
	}
 
	int count = 0;
	for (int i = 1; i * i <= remainder; ++i)
	{
		if (remainder % i == 0)
		{
			answer[count++] = i;
 
			if (i != remainder / i)
			{
				answer[count++] = remainder / i;
			}
		}
	}
 
	std::sort(answer, answer + count);
	for (int i = 1; i < count; ++i)
	{
		std::cout << answer[i] << " ";
	}
 
	return 0;
}
 

처음엔 arr[0]까지 계산하려고 했는데 그럼 너무 많은 크기가 있어 시간초과입니다.

arr에 모든 수를 M으로 나눠야 하고 M이 필요하기 때문에 서로 빼기만 한다면 나머지가 필요 없기 때문에

나눈다음 그 수의 최대 공약수를 구해놓는다면 최대공약수의 약수만큼 나옵니다. 

1은 필요없기 때문에 모두가 가지고 있는 약수이자 맨 처음나오는 수인 1을 빼고 제출합니다.