[c++] 백준-최대공약수 하나 빼기 ( 누적합, 정수론)

1. 문제

2. 입출력 및 예제

---

3. 문제 해설

하나를 뺐을 때 최대공약수가 최대가 되어야한다. 

이 문제를 해결하기 위해서는 누적합의 개념을 적용해야한다. 사실 누적합은 누적해서 합을 구하는 것에만 쓰이는 개념은 아니다. 여태까지 나온 값들의 대표값을 의미하기도 한다. 그래서 세그먼트 트리나 인덱스드 트리로도 풀 수 있을 거 같은 문제였다. 

 

핵심 아이디어는 다음과 같다. 

 

LtoR : 왼쪽서부터 최대 공약수를 구해 저장하는 배열

RtoL : 오른쪽서부터 최대 공약수를 구해 저장하는 배열

 

두 배열이 존재한다면 예제의 경우 다음과 같다. 

 

index	0	1	2	3	4
nums	8	12	24	36	48
LtoR	8	4	4	4	4
RtoL	12	12	12	12	48

세 가지의 경우로 나눌 수 있겠다. 

 

먼저 맨 처음 수가 빠지는 경우 12 24 36 48의 최대 공약수를 구해야하므로 RtoL[1]이 되겠다. 

두번째로 맨 마지막 수가 빠지는 경우 8 12 24 36의 최대 공약수를 구해야하므로 LtoR[N-2]가 답이 되겠다. 

 

세번째로 가운데의 수가 빠지는 경우이다. 

이 때는 나보다 이전까지의 공약수와 나 이후의 공약수의 최대공약수를 구해줘야한다. 

24가 빠진다고 생각해보면 8 12까지의 최대공약수와 36과 48의 최대공약수를 구해줘야하므로 

LtoR[1]과 RtoL[3]의 최대공약수를 구해주면 되는 것이다. 이런 방식으로 최대가 될 때의 최대공약수와 그 수를 저장해준다. 

 

또한 마지막에 최대가 될 때의 최대공약수가 뺀 수의 약수가 되는 지 모듈러 연산을 통해 확인해준 후 출력해주면 된다. 

최대공약수를 구하는 방법은 유클리드 호제법을 사용한다. 

---

#pragma warning (disable : 4996)

#include <cstdio>

using namespace std;
int N; // 수의 개수
int nums[1000002];
int LtoR[1000002];
int RtoL[1000002];
int gcd(int a, int b) {
	while (b) {
		int c = a % b;
		a = b;
		b = c;
	}
	return a;
}
void makeGcds() {
	LtoR[0] = nums[0];
	RtoL[N - 1] = nums[N - 1];
	for (int i = 1; i < N; i++) {
		LtoR[i] = gcd(nums[i], LtoR[i - 1]);
		RtoL[N - 1 - i] = gcd(nums[N - 1 - i], RtoL[N - i]);
	}
}

void sol() {
	int ans = RtoL[1]; // 첫번째를 뺏을 때의 경우
	int ansNum = nums[0];

	for (int i = 1; i < N - 1; i++) {
		int temp = gcd(LtoR[i - 1], RtoL[i + 1]);
		if (temp > ans) {
			ans = temp;
			ansNum = nums[i];
		}
	}

	if (LtoR[N - 1] > ans) {
		ans = LtoR[N - 1];
		ansNum = nums[N - 1];
	} // 마지막 수 뺐을 때의 경우

	if ((ansNum % ans) == 0) {
		// 배수라는 뜻이므로
		puts("-1");
	}
	else {
		printf("%d %d",ans, ansNum);
	}
}
int main() {
	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		scanf("%d", &nums[i]);
	}

	makeGcds();

	sol();

	return 0;
}