BOJ : 14476 최대공약수 하나 빼기

---

[BOJ 14476(G2)리뷰]

N개의 정수가 주어지고 그 중 하나를 뺐을때 남은 정수들의 최소공배수가 최대가 되는 경우를 구해야 한다.

예를들어 [8,12,24,36,48]이라는 정수가 주어졌을 때, 8을 뺀다면 나머지 [12,24,36,48]의 최대공약수가 12로 가장 크다.

N의 범위는 4<=N<=1,000,000 이다. 하나를 빼고, 남은 수들의 최대공약수를 완전탐색 해보는 방법으로는 시간초과를 맞게 된다. 따라서 다른 알고리즘을 생각해야 한다.

먼저, 최대공약수 부터 빠르게 구할 수 있어야 한다. 일반적으로 여러개의 정수의 최대공약수를 구할 때 가장 작은 소수부터 나누는 방법을 선택하지만 이렇게 한다면 값이 큰 정수를 연산할때 매우 오랜 시간이 걸리게 된다.

따라서 유클리드 호제법을 이용하여 최대공약수를 구했다.

(a<b)일 때, GCD(a,b) = GCD(b,a%b) 라는 성질을 이용하는 것이다. 그리고 이것을 응용하여 3개 이상 정수의 최대공약수도 구할 수 있다. GCD(a,b,c) = GCD(GCD(a,b),c) 를 만족한다.

이제, 이 방법을 값을 하나씩 빼어, 나머지 수들의 최대공약수를 구해야한다. 이건 어떻게 구현해야 할까?

답은 "누적합"개념을 이용한 "누적 최대공약수"를 통해 해결했다. 두가지 방향의 GCD를 담을 배열을 선언하고, 한번은 왼쪽에서 오른쪽 방향으로(->) 누적된 값들의 최대공약수를 구한다. 그리고 다음엔 오른쪽에서 왼쪽으로 (<-) 누적된 값들의 최대 공약수를 담는다.

예를들어 [8,12,24,36,48] 이라면 LEFT GCD는 [8] -> [8,4] -> [8,4,4] 이런식으로 흘러갈 것이다.

RIGHT GCD는 [48] -> [12,48] -> [12,12,48] 이런식으로 값을 채워나가게 된다.

그렇다면 이제 [8,12,24,36,48]의 배열에서 가운데에 있는 24라는 값을 뺐을때의 최대 공약수를 구해보자.

24의 index를 3이라 했을때 GCD(LEFT GCD[2],RIGHT[4])가 24를 제외한 나머지 수들의 최대공약수가 되게 된다.

이 알고리즘을 이용하여 N개의 수들을 하나씩 빼가며 최대공약수를 확인하고, 최대공약수가 최대가 되었을때의 값들을 기록하여 출력해주면 된다.

/*
	21.01.14
	BOJ : 14476 최대공약수 하나 빼기 (https://www.acmicpc.net/problem/14476)
	정수론/유클리드 호제법
*/
#include <bits/stdc++.h>
using namespace std;

int leftGcd[1000002];
int rightGcd[1000002];
int arr[1000002];

// gcd(a,b) = gcd(b,a%b)
int gcd(int a, int b) {
	while (b != 0) {
		int r = a % b;
		a = b;
		b = r;
	}

	return a;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);

	int N;
	cin >> N;


	for (int i = 1; i <= N;i++) {
		cin >> arr[i];
	}

	leftGcd[1] = arr[1];
	rightGcd[N] = arr[N];

	for (int i = 2; i <= N; i++) {
		leftGcd[i] = gcd(leftGcd[i-1],arr[i]);
	}

	for (int i = N-1; i >= 1; i--) {
		rightGcd[i] = gcd(rightGcd[i + 1], arr[i]);
	}

	int ans = 0;
	int ansGcd = 0;
	for (int i = 1; i <= N; i++) {
		int Gcd = gcd(leftGcd[i - 1], rightGcd[i + 1]);

		if (arr[i] % Gcd != 0 && Gcd>ansGcd) {
			ans = arr[i];
			ansGcd = Gcd;
		}
	}

	if (ans == 0 && ansGcd == 0) {
		cout << -1;
	}
	else {
		cout << ansGcd << " " << ans;
	}
	
	return 0;
}