BOJ 14476 - 최대공약수 하나 빼기 링크
(2024.03.23 기준 G2)

문제

$N$개의 자연수가 주어진다. 이 중 임의의 수 하나를 뺏을 때, 나머지 수들의 최대공약수가 뺀 수의 약수가 되지 않으면, 최대공약수와 뺀 수를 조건을 만족하는 쌍이라고 하자.
조건을 만족하는 쌍 중에서 가장 큰 최대공약수를 갖는 쌍을 출력

알고리즘

유클리드 호제법 + (누적 합 or 세그먼트 트리)

풀이

문제를 요약하면 다음과 같다

$f(l,r)$을 $A_l$, $A_{l+1}$, $\dots$, $A_r$의 최대공약수라고 하자.
모든 $i(0 \le i < N)$에 대해서, $A_i$를 $\gcd(f(0,i-1), f(i+1,N-1))$로 나눌 수 있는지 확인하자.

$f(l,r)$을 어떻게 빠르게 구할 수 있을까?
$\gcd(l, r)$과 $\gcd(r, l)$은 같다. 즉, 교환법칙이 성립한다.

이와 같은 점을 이용해서 두 가지 방법으로 풀 수 있다.

세그먼트 트리

구간의 정보는 세그먼트 트리를 이용해 관리할 수 있다. 이 문제에선 수의 업데이트가 없기 때문에, 간단한 세그먼트 트리로 풀 수 있게 된다. 너무나도 간단한 풀이이기 때문에 설명은 생략하겠다.

누적 합 배열

$\gcd(f(0,i-1), f(i+1,N-1))$에서 두 구간을 잘보면 두 구간을 잘보면 인덱스 0부터 시작 아니면 인덱스 N-1로 끝나는 구간이다. 그러므로 $ltor(i): \gcd(A_0, A_1, \dots, A_i)$, $rtol(i): \gcd(A_i, A_{i+1}, \dots, A_{N-1})$인 두 누적 gcd 배열을 만들어주면 된다.

코드

세그먼트 트리

• C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1'000'000, MAXM = 1 << (int)ceil(log2(MAXN) + 1);

ll A[MAXN], T[MAXM];

// 유클리드 호제법
ll gcd(ll a, ll b){
    ll r = a % b;
    if (r) return gcd(b, r);
    return b;
}

// l과 r의 gcd 반환
ll merge(ll l, ll r){
    if (!l) return r; // l이 빈 값이면 r을 반환
    if (!r) return l; // r이 빈 값이면 l을 반환
    return gcd(l, r);
}

// 양쪽 구간을 합쳐서 저장
void pull(int nd){
    T[nd] = merge(T[nd << 1], T[nd << 1 | 1]);
}

// 세그먼트 트리 만들기
void init(int nd, int st, int en){
    if (st == en){
        T[nd] = A[st];
        return;
    }
    int mid = (st + en) >> 1;
    init(nd << 1, st, mid);
    init(nd << 1 | 1, mid + 1, en);
    pull(nd);
}

// [l, r] 범위의 값 구하기
ll query(int nd, int st, int en, int l, int r){
    if (r < st || en < l) return 0;
    if (l <= st && en <= r) return T[nd];
    int mid = (st + en) >> 1;
    return merge(query(nd << 1, st, mid, l, r), query(nd << 1 | 1, mid + 1, en, l, r));
}

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

    int N; cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i];

    /* f(l, r): [l, r] 구간의 수들의 최대공약수라고 한다면
    모든 i에 대해서 A_i가 gcd(f(0,i-1), f(i+1,N-1))로 나누어지는지 확인하면 된다. (0-based index)
    빠르게 구간의 정보를 확인하기 위해선 세그먼트 트리를 사용하면 된다. */

    // 세그먼트 트리
    init(1, 0, N - 1);

    // 모든 i에 대해 확인
    ll ans1 = -1, ans2 = -1;
    for (int i = 0; i < N; i++){
        ll res = merge(query(1, 0, N - 1, 0, i - 1), query(1, 0, N - 1, i + 1, N - 1));
        if (A[i] % res && ans1 < res){
            ans1 = res;
            ans2 = A[i];
        }
    }

    if (~ans1) cout << ans1 << ' ' << ans2;
    else cout << -1;
}

• Python (PyPy3)

import sys; input = sys.stdin.readline
from math import ceil, log2

# 유클리드 호제법
def gcd(a, b):
    r = a % b
    if r:
        return gcd(b, r)
    return b

''' TLE 때문에 삭제
# l과 r의 gcd 반환
def merge(l, r):
    if not l: # l이 빈 값이면 r을 반환
        return r
    if not r: # r이 빈 값이면 l을 반환
        return l
    return gcd(l, r) '''

''' TLE 때문에 삭제
# 양쪽 구간을 합쳐서 저장
def pull(nd):
    T[nd] = merge(T[nd << 1], T[nd << 1 | 1]) '''

# 세그먼트 트리 만들기
def init(nd, st, en):
    if st == en:
        T[nd] = A[st]
        return
    mid = (st + en) >> 1
    init(nd << 1, st, mid)
    init(nd << 1 | 1, mid + 1, en)
    ''' TLE 때문에 삭제
    pull(nd) '''
    T[nd] = gcd(T[nd << 1], T[nd << 1 | 1])

# [l, r] 범위의 값 구하기
def query(nd, st, en, l, r):
    if r < st or en < l:
        return 0
    if l <= st and en <= r:
        return T[nd]
    mid = (st + en) >> 1
    ''' TLE 때문에 삭제
    return merge(query(nd << 1, st, mid, l, r), query(nd << 1 | 1, mid + 1, en, l, r)) '''
    le = query(nd << 1, st, mid, l, r)
    ri = query(nd << 1 | 1, mid + 1, en, l, r)
    if not le:
        return ri
    if not ri:
        return le
    return gcd(le, ri)

N = int(input())
A = list(map(int, input().split()))

''' f(l, r): [l, r] 구간의 수들의 최대공약수라고 한다면
모든 i에 대해서 A_i가 gcd(f(0,i-1), f(i+1,N-1))로 나누어지는지 확인하면 된다. (0-based index)
빠르게 구간의 정보를 확인하기 위해선 세그먼트 트리를 사용하면 된다. '''

# 세그먼트 트리
T = [0] * (1 << ceil(log2(N) + 1))
init(1, 0, N - 1)

# 모든 i에 대해 확인해서 정답 갱신
ans1 = ans2 = -1
for i in range(N):
    ''' TLE 때문에 삭제
    res = merge(query(1, 0, N - 1, 0, i - 1), query(1, 0, N - 1, i + 1, N - 1)) '''
    le = query(1, 0, N - 1, 0, i - 1)
    ri = query(1, 0, N - 1, i + 1, N - 1)
    if not le:
        res = ri
    elif not ri:
        res = le
    else:
        res = gcd(le, ri)
    if A[i] % res and ans1 < res:
        ans1 = res
        ans2 = A[i]

if ~ans1:
    print(ans1, ans2)
else:
    print(-1)

누적 합

• C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// 유클리드 호제법
ll gcd(ll a, ll b){
    ll r = a % b;
    if (r) return gcd(b, r);
    return b;
}

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

    int N; cin >> N;
    ll A[N]; for (int i = 0; i < N; i++) cin >> A[i];

    /* f(l, r): [l, r] 구간의 수들의 최대공약수라고 한다면
    모든 i에 대해서 A_i가 gcd(f(0,i-1), f(i+1,N-1))로 나누어지는지 확인하면 된다. (0-based index)
    두 구간을 잘보면 인덱스 0부터 시작 아니면 인덱스 N-1로 끝나는 구간이기 때문에
    시작부터 누적 gcd, 끝부터 누적 gcd인 두 누적 배열을 구해놓으면 된다. */

    ll ltor[N]; // 시작부터 누적 gcd (0-based index)
    ltor[0] = A[0];
    for (int i = 1; i < N; i++) ltor[i] = gcd(ltor[i - 1], A[i]);

    ll rtol[N]; // 끝부터 누적 gcd (0-based index)
    rtol[N - 1] = A[N - 1];
    for (int i = N - 2; i >= 0; i--) rtol[i] = gcd(rtol[i + 1], A[i]);

    // 모든 i에 대해 확인
    ll res, ans1 = -1, ans2 = -1;
    for (int i = 0; i < N; i++){
        if (i == 0) res = rtol[i + 1]; // [i+1, N-1] 구간의 gcd
        else if (i == N - 1) res = ltor[i - 1]; // [0, i-1] 구간의 gcd
        else res = gcd(ltor[i - 1], rtol[i + 1]); // [0, i-1] 구간의 gcd와 [i+1, N-1] 구간의 gcd의 gcd
        if (A[i] % res && ans1 < res){
            ans1 = res;
            ans2 = A[i];
        }
    }

    if (~ans1) cout << ans1 << ' ' << ans2;
    else cout << -1;
}

• Python

import sys; input = sys.stdin.readline

# 유클리드 호제법
def gcd(a, b):
    r = a % b
    if r:
        return gcd(b, r)
    return b

N = int(input())
A = list(map(int, input().split()))

''' f(l, r): [l, r] 구간의 수들의 최대공약수라고 한다면
모든 i에 대해서 A_i가 gcd(f(0,i-1), f(i+1,N-1))로 나누어지는지 확인하면 된다. (0-based index)
두 구간을 잘보면 인덱스 0부터 시작 아니면 인덱스 N-1로 끝나는 구간이기 때문에
시작부터 누적 gcd, 끝부터 누적 gcd인 두 누적 배열을 구해놓으면 된다. '''

ltor = [0] * N # 시작부터 누적 gcd (0-based index)
ltor[0] = A[0]
for i in range(1, N):
    ltor[i] = gcd(ltor[i - 1], A[i])

rtol = [0] * N # 끝부터 누적 gcd (0-based index)
rtol[N - 1] = A[N - 1]
for i in range(N - 2, -1, -1):
    rtol[i] = gcd(rtol[i + 1], A[i])

# 모든 i에 대해 확인
ans1 = ans2 = -1
for i in range(N):
    if i == 0:
        res = rtol[i + 1] # [i+1, N-1] 구간의 gcd
    elif i == N - 1:
        res = ltor[i - 1] # [0, i-1] 구간의 gcd
    else:
        res = gcd(ltor[i - 1], rtol[i + 1]) # [0, i-1] 구간의 gcd와 [i+1, N-1] 구간의 gcd의 gcd
    if A[i] % res and ans1 < res:
        ans1 = res
        ans2 = A[i]

if ~ans1:
    print(ans1, ans2)
else:
    print(-1)