(BOJ) 14476 최대공약수 하나 빼기

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

 

 

문제 풀이:

왼쪽부터 gcd 값 기록하는 배열 하나

오른쪽부터 gcd 값 기록하는 배열 하나

만들기

 

ex) 입력: 8 12 24 36 48

입력 값	8	12	24	36	48
left to right	8	4	4	4	4
right to left	4	12	12	12	48

만약 arr[0]인 8을 뺀다면 rtol[1]이 최대공약수가 된다.

만약 arr[1]인 12를 뺀다면 gcd(ltor[0],rtol[2])가 최대공약수가 된다.

즉, 해당 위치의 직전 최대공약수와 이후 최대공약수의 최대공약수가 전체의 최대공약수가 된다. ㅎㅎ

 

소스코드:

int n, arr[1000001],ltor[1000001],rtol[1000001],res1,res2;
using namespace std;

int gcd(int a, int b) {
	if (b == 0) return a;
	gcd(b, a%b);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	ltor[0] = arr[0];
	for (int i = 1; i < n; i++) {
		ltor[i] = gcd(ltor[i - 1], arr[i]);
	}
	rtol[n - 1] = arr[n - 1];
	for (int i = n-2; i >=0; i--) {
		rtol[i] = gcd(rtol[i+1], arr[i]);
	}
	int t = rtol[1];
	if (arr[0] < t || gcd(arr[0], t) != t) {
		res1 = t;
	}
	for (int i = 1; i < n-1; i++) {
		t = gcd(ltor[i - 1], rtol[i + 1]);
		if (arr[i] < t || gcd(arr[i], t) != t) {
			if (res1 < t) {
				res1 = t;
				res2 = i;
			}
		}
	}
	if (arr[n-1] < ltor[n-2] || gcd(arr[n-1], ltor[n-2]) != t) {
		if (res1 < t) {
			res1 = ltor[n-2];
			res2 = n-2;
		}
	}
	if (res1 == 0) cout << "-1\n";
	else cout << res1 << " " << arr[res2] << '\n';
	return 0;
}