검문 (feat. 백준, 2981번)

검문
https://www.acmicpc.net/problem/2981

2981번: 검문

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/2981
#include <iostream>
#include <set>
#include <cmath>
using namespace std;
inline int gcd(register int a, register int b) {
	return a % b ? gcd(b, a % b) : b;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N, M, arr[100] = { 0 };
	set<int> ans;
	cin >> N;
	for (register int i = 0; i < N; ++i)
		cin >> arr[i];
	M = abs(arr[1] - arr[0]);
	for (register int i = 2; i < N; ++i)
		M = gcd(M, abs(arr[i] - arr[i - 1]));
	for (register int i = 1; i * i <= M; ++i)
		if (M % i == 0) {
			ans.insert(i);
			if (i != M / i)
				ans.insert(M / i);
		}
	for (auto& a : ans)
		if (a != 1)
			cout << a << " ";
	return 0;
}
// *&)*@*

여러 반례들을 보고 풀었습니다. 난이도만큼 어려운 문제입니다.