백준 14476번 : 최대공약수 하나 빼기 (c++)

https://www.acmicpc.net/problem/14476

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

문제

정수 A가 B로 나누어 떨어지면, B는 A의 약수이고 A는 B의 배수이다.

최대공약수란 정수의 공통된 약수 중 가장 큰 수를 말한다. 예를 들어, 12와 8의 공통된 약수 1, 2, 4 중에서 가장 큰 것은 4이기 때문에 12와 8의 최대공약수는 4이다.

N개의 정수 중에서 임의의 수 K를 뺐을 때, 나머지 N-1개의 최대공약수가 가장 커지는 것을 찾는 프로그램을 작성하시오. 이때, 최대공약수는 K의 약수가 되면 안 된다.

예를 들어, 정수 8, 12, 24, 36, 48에서 8을 빼면 나머지 12, 24, 36, 48의 최대공약수는 12가 되고, 12는 빠진 수 8의 약수가 아니기 때문에 정답이 될 수 있다. 이때, 다른 수를 빼도 최대공약수가 8보다 커질 수 없다.

하지만, 8, 12, 20, 32, 36의 경우에는 그 무엇을 빼더라도 나머지 수의 최대공약수가 K의 약수가 되기 때문에, 정답을 구할 수 없다.

N개의 수가 주어졌을 때, 정수 하나를 빼서 만들 수 있는 가장 큰 최대공약수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수 N (4 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. 각각의 수는 20억을 넘지 않는 자연수이다.

출력

첫째 줄에 정수 하나를 빼서 만들 수 있는 가장 큰 최대공약수를 출력하고, 공백을 출력한 다음 뺀 수를 출력한다. 

뺀 수를 K라고 했을 때, 나머지 수의 최대공약수가 K의 약수가 되면 안 된다.

만약 정답이 없는 경우에는 -1을 출력한다.

예제 입력 1 
5
8 12 24 36 48
예제 출력 1 
12 8
예제 입력 2 
5
8 12 20 32 36
예제 출력 2 
-1

#include <iostream>
#include <vector>
using namespace std;
//누적합 gcdLtoR, gcdRtoL
int gcd(int a, int b) {
	while (b != 0) {
		int r = a % b;
		a = b;
		b = r;
	}
	return a;
}
int gcdLtoR[1000001];
int gcdRtoL[1000001];
int N, a;
vector <int> num;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> a;
		num.push_back(a);
	}
	gcdLtoR[0] = num[0];
	gcdRtoL[N - 1] = num[N - 1];
	for (int i = 1; i < N; i++)
	{
		gcdLtoR[i] = gcd(gcdLtoR[i - 1], num[i]);
		gcdRtoL[num.size() - i - 1] = gcd(gcdRtoL[num.size() - i], num[num.size() - i - 1]);
	}
	int maxGcd = 0, number = -1;
	if (maxGcd < gcdRtoL[1]) {
		maxGcd = gcdRtoL[1];
		number = num[0];
	}
	for (int i = 1; i < N - 1; i++) {
		int temp = gcd(gcdLtoR[i - 1], gcdRtoL[i + 1]);
		if (maxGcd < temp) {
			maxGcd = temp, number = num[i];
		}
	}
	if (maxGcd < gcdLtoR[N - 1]) {
		maxGcd = gcdLtoR[N - 2];
		number = num[N - 1];
	}

	/*for (int i = 0; i < N; i++)
	{
		cout << gcdLtoR[i] << " " << gcdRtoL[i]<<"\n";
	}*/
	if (number % maxGcd == 0) {
		cout << -1;
		return 0;
	}
	cout << maxGcd << " " << number;
	return 0;
}