160. 최대공약수 하나빼기

백준

1. Python

import sys, math
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
left_gcd = [0] * (n + 1)
right_gcd = [0] * (n + 1)
left_gcd[0] = arr[0]
right_gcd[n - 1] = arr[n - 1]
for i in range(1, n):
    left_gcd[i] = math.gcd(left_gcd[i - 1], arr[i])
    
for i in range(n - 2, -1, -1):
    right_gcd[i] = math.gcd(right_gcd[i + 1], arr[i])
ans = []
for i in range(n):
    left = left_gcd[i - 1]
    right = right_gcd[i + 1]
    res = math.gcd(left, right)
    if arr[i] % res == 0:
        continue
    ans.append((res, arr[i]))

ans.sort(reverse=True)
print(' '.join(map(str, ans[0])) if ans else -1)

• [8,12,24,36,48]이라는 정수가 주어졌을 때, 8을 뺀다면 나머지 [12,24,36,48]의 최대공약수가 12로 가장 크다.

import sys
input = sys.stdin.readline


def gcd(a, b):
    if a >= b:
        if a % b == 0:
            return b
        else:
            return gcd(b, a % b)
    elif a < b:
        if b % a == 0:
            return a
        else:
            return gcd(a, b % a)

n = int(input())
arr = list(map(int, input().rstrip().split()))
# 누적 gcd
left = [1] * n
right = [1] * n
for i in range(n):
    if i == 0:
        left[i] = arr[i]
        right[-i-1] = arr[-i-1]
        continue
    left[i] = gcd(left[i-1], arr[i])
    right[-i-1] = gcd(right[-i], arr[-i-1])

results = 1
num = 0
for i in range(n):
    x = arr[i]
    if i == 0:
        if x % right[i+1] != 0:
            num = x
            results = max(results, right[i+1])
    elif i == n-1:
        if x % left[i-1] != 0:
            num = x
            results = max(results, left[i-1])
    else:
        gcd_tmp = gcd(left[i-1], right[i+1])
        if x % gcd_tmp != 0:
            num = x
            results = max(results, gcd_tmp)
if results != 1:
    print(results, num)
else:
    print(-1)

2. Java

import java.io.*;
import java.util.*;

public class Main {
    private static int N;
    private static int[] A;
    private static int[] leftGcd, rightGcd;
    private static int answer = -1, who;
    public static void main(String[] args) throws Exception {       
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

        A = new int[N + 2];
        leftGcd = new int[N + 2];
        rightGcd = new int[N + 2];
        st = new StringTokenizer(br.readLine());
        for (int i = 1 ; i <= N ; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        for (int i = 1 ; i <= N ; i++) {
            leftGcd[i] = gcd(leftGcd[i - 1], A[i]);
        }
        for (int i = N ; i >= 1 ; i--) {
            rightGcd[i] = gcd(rightGcd[i + 1], A[i]);
        }
        for (int i = 1 ; i <= N ; i++) {
            int curGcd = gcd(leftGcd[i - 1], rightGcd[i + 1]);
            if (A[i] % curGcd == 0) continue;
            if (answer < curGcd) {
                answer = curGcd;
                who = A[i];
            }
        }
        if (answer == -1) {
            System.out.println(answer);
        }
        else {
            System.out.println(answer + " " + who);
        }
    }

    private static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

}