14476 최대공약수 하나 빼기

 

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

최대공약수를 구하는 것에 사용되는 유클리드 호제법에는 결합 법칙이 적용된다.

예를 들어 GCD(4,18, 14)의 결과는 GCD(GCD(4,18), 14)의 결과와 같다.

그리고 이 문제와 같이 배열에서 하나의 수를 제거했을 때의 최대공약수는 위 사실을 이용하면 간단히 해결할 수 있다.

 

a	b	c	d	e	f
a	gcd(a,b)	gcd(a,b,c)	gcd(a,b,c,d)	gcd(a,b,c,d,e)	gcd(a,b,c,d,e,f)
gcd(a,b,c,d,e,f)	gcd(b,c,d,e,f)	gcd(c,d,e,f)	gcd(d,e,f)	gcd(e,f)	f

위와 같이 (a, b, c, d, e, f)가 주어졌다고 하자.

이때 이 배열에서 c를 제외하였을 때의 최대공약수를 구하는 식인 GCD(a, b, d, e, f)는 결합 법칙에 따라 GCD(GCD(a, b), GCD(d, e, f))와 같다.

 

즉, 어떤 임의의 수 x를 제외하였을 때의 최대공약수는 배열의 처음부터 x 이전의 수까지의 최대공약수와 배열에서 x 이후의 수부터 배열의 끝에 위치한 수의 최대공약수를 구하면 손쉽게 구할 수 있는 것을 확인할 수 있다.

 

따라서 이 문제는 주어지는 수의 정방향과 역방향으로 각각 누적해서 최대 공약수를 미리 구한다면 임의의 수를 1개 제외하였을 때의 최대공약수를 바로 구할 수 있게 된다.

 

 

#include <iostream>
#include <vector>

using namespace std;

vector<int> vec;
vector<int> left_sum;
vector<int> right_sum;
int gcd(int a, int b) {
	int temp;
	while (b) {
		temp = a % b;
		a = b;
		b = temp;
	}
	return a;
}

int main(void)
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	int n;
	cin >> n;

	vec.resize(n);
	left_sum.resize(n);
	right_sum.resize(n);

	for (int i = 0; i < n; ++i) {
		cin >> vec[i];
	}

	left_sum[0] = vec[0];
	for (int i = 1; i < n; ++i) {
		left_sum[i] = gcd(left_sum[i - 1], vec[i]);
	}

	right_sum[n - 1] = vec[n - 1];
	for (int i = n - 2; i >= 0; --i) {
		right_sum[i] = gcd(right_sum[i + 1], vec[i]);
	}

	pair<int, int> res{-1, 0};
	int candidate;

	for (int i = 0; i < n; ++i) {
		if (i == 0) {
			candidate = right_sum[i + 1];
		}
		else if (i == n - 1) {
			candidate = left_sum[i - 1];
		}
		else {
			candidate = gcd(left_sum[i - 1], right_sum[i + 1]);
		}

		if (gcd(candidate, vec[i]) != candidate && candidate > res.first) {
			res = { candidate, vec[i] };
		}
	}

	if (res.first == -1) {
		cout << -1;
	}
	else {
		cout << res.first << ' ' << res.second;
	}

	return 0;
}