백준 2981 검문

www.acmicpc.net/problem/2981

2981번: 검문

ar 배열에 입력받은 수들을 정렬해주고

어떤 수 ar[i] = 몫*나눈값+나머지 이므로 나머지를 처리해줘야 하니

ar[i] - ar[i-1] = 나눈값(몫-몫2) + (나머지-나머지) 이다

나눌 값들은 각각에 배열들에 대해 최대공약수를 구해서 그 최대공약수의 약수들로 나눠주면 같은 나머지가 출력된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int GCD(int x, int y) {
	if (y == 0) return x;
	return GCD(y, x % y);
}

int main() {
	int n, gcd;
	vector<int> ar, ans;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x; cin >> x;
		ar.push_back(x);
	}
	sort(ar.begin(), ar.end());

	gcd = ar[1] - ar[0];
	for (int i = 2; i < n; i++) gcd = GCD(gcd, ar[i] - ar[i - 1]);

	for (int i = 2; i * i <= gcd; i++) {
		if (gcd % i == 0) {
			ans.push_back(i); ans.push_back(gcd / i); 
		}
	}

	ans.push_back(gcd);
	sort(ans.begin(), ans.end());
	ans.erase(unique(ans.begin(), ans.end()), ans.end());
	for (int i = 0; i < (int)ans.size(); i++) cout << ans[i] << ' ';
	

	return 0;
}

유클리드 호제법을 전부 돌리고 나서 그 최대공약수에 대해 약수를 구해야 하는데 최댓값이 10억이라 그냥 구하면 TLE가 난다.

	for (int i = 2; i * i <= gcd; i++) {
		if (gcd % i == 0) {
			ans.push_back(i); ans.push_back(gcd / i); 
		}
	}

약수구하는 로직을 제곱을 통해 최적화를 해주고
포문을 1이 아닌 2부터 돌리니까 마지막 최대공약수가 포함되지 않는다. 따로 처리해줘야 한다.

 

	sort(ans.begin(), ans.end());
	ans.erase(unique(ans.begin(), ans.end()), ans.end());

각각의 약수들에 대해 정렬해서 unique함수를 통해 중복되는 수를 제거해주면 AC를 받는다.