[2981] 검문

 

 

처음에는 시간 초과 생각 안하고

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

int N;
int A[100];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	printf("%d", 5 % 6);
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}

	sort(A, A + N);
	

	int R;
	for (int i = 2; i <= A[N-1]; i++) { // M은 1보다 크고 제일 작은 수보다 작음
		bool isit = true;
		R = A[0] % i;
		for (int j = 1; j < N; j++) {
			if (A[j] % i != R) { // 하나라도 나머지가 다르면
				isit = false;
				break;
			}
		}
		if (isit == true) { // 만약 j for문을 다 돌았으면 나머지가 다 같앗단거임
			printf("%d ", i);
		}
	}
	 
}

이렇게 풀었더니 계속 시간초과 나왔다

ㅜㅜ

 

이런 식으로 접근하면 안됐었다

 

자세한 건 직접 썼음

M으로 나누면 나머지가 R로 똑같음

M : B-A, C-B, D-C ... 의 공약수

B-A, C-B, D-C : M의 배수

 

유클리드 호제법으로 최대공약수 구함

최대공약수의 약수들(=M)을 구해야함(1 제외)

for문 전체를 돌리면 시간 초과이므로 최대공약수의 제곱근만큼만 돌림

순서대로 출력해야하므로 중복을 허용하지 않고 자동 정렬되는 집합(set) 사용 

 

#include <iostream>
#include <algorithm>
#include <math.h>
#include <set>
using namespace std;

int N;
int A[100];
int B[99];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}
	sort(A, A + N); // A 배열 오름차순 정렬


	for (int i = 0; i < N-1; i++) { // A배열 차이 B 배열에 넣기
		B[i] = A[i + 1] - A[i];
	}
	sort(B, B + N - 1); // B 배열 오름차순 정렬


	int R = B[0];
	for (int i = 0; i < N - 2; i++) {
		int big = B[i+1]; int small = R;
		while (1) {
			R = big % small;
			if (R == 0) {
				R = small;
				break;
			}
			big = small; small = R;
		}
	} 
	// R의 공약수 구하면 됨(1 제외)

	// 약수 구하기
	set<int> myset;
	for (int i = 1; i * i <= R; i++) {
		if (R % i == 0) {
			myset.insert(i);
			myset.insert(R / i);
		}
	}
	myset.erase(1); // M은 1보다 크므로 없앰

	set<int> ::iterator iter;
	for (iter = myset.begin(); iter != myset.end(); iter++)
	{
		printf("%d ", *iter);
	}
}