BOJ 2981 - 검문

* BOJ 2981 - 검문 (https://www.acmicpc.net/problem/2981)

[ 분류 - GCD ]

  수학 개념이 필요한 문제다.

  주어지는 N개의 수를 정렬한 수열의 결과를 a1, a2, ..., an 이라 하자.

  임의의 정수 M으로 나눴을 때 수열의 나머지를 m라고 할 때, 수식을 아래처럼 나타낼 수 있다.

  이에 대해 근접한 원소끼리 차이를 정리해보면,

...

  서로 다른 두 원소 차이에 대해 "약수"로 M이 들어가 있는 것을 확인할 수 있다. 따라서 이 차이에 대해 최대공약수를 구하여 그것의 약수를 모두 출력하면 된다.

- 코드

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int gcd(int p, int q) {
	if (q == 0) return p;
	return gcd(q, p % q);
}
int main() {
	int N,g,i,A[100];
	scanf("%d", &N);
	for (i = 0; i < N;i++)
		scanf("%d", &A[i]);
	sort(A, A + N);
	g = A[1] - A[0];
	for (i = 1; i < N - 1; i++)
		g = gcd(g, A[i + 1] - A[i]);
	vector<int> ans;
	for(i=1;i*i<=g;i++)
		if (!(g%i)) {
			ans.push_back(i);
			if(i != g/i) ans.push_back(g/i);
		}
	sort(ans.begin(), ans.end());
	for (int& a : ans)
		if(a!= 1) printf("%d ", a);
	return 0;
}