gcd와 set

• 먼저 당연한 사실을 언급하면, 집합에 원소가 추가될때마다 그 집합의 gcd는 작아진다.
• 우선, 중복된 수는 몇 개가 있으나 의미가 없다. 중복된 수를 제거하고 나면, 원소 개수는 최대 5000이하로 줄어든다.
  • 유일하게 중복된 수의 개수가 의미있는 경우가 있기는 하다. 수가 전부 똑같을 경우일때, N=1이면 A_1 과 공집합으로 나누게 되므로 답은 A_1 이고, N>1 일때는 두 개의 집합으로 나눌수 있으므로 답이 A_1 + A_1 = 2*A_1 이 된다.
• 원소의 개수가 5000이고, 값의 범위도 5000라서 어느정도 느린 알고리즘을 구현해도 시간 안에 돌아간다.
• 간단한 방법은 $\text{gcd}_A(S') $ 를 x, $ \text{gcd}_A(S \setminus S')$ 를 y라고 할때, x를 1~5000 까지로 각각 고정시켜보면서 y를 구하는 방법이 가능하다. 이것도 다시 몇가지 아이디어가 나올수 있는데,
  • [1] x를 고정했을때, y의 최댓값을 계산해서 찾는 방법.
    • $\text{gcd}_A(S') $ 이 x이면, S'이 모든 x의 배수를 포함하는 집합일때, $ \text{gcd}_A(S \setminus S')$ 가 최대가 된다.
    • n개의 원소중에서 x의 배수가 아닌 값들만 뽑고, 그것들의 gcd를 구하는 것은 O(nlogn). 이것을 모든 x에 대해서 계산해야 하므로 총 O(n^2logn). 실제로 돌려보면 2564ms 정도에 돌아간다.
  • [2] x와 y를 고정했을때, 이것을 만족하는 S' 이 존재하는지를 확인하는 방법.
    • 전체 집합을, x의 배수의 집합과 y의 배수의 집합으로 분할할 수 있는지를 확인하는 것과 동일하다.
    • {x의 배수의 개수} + {y의 배수의 개수} - {lcm(x,y)의 배수의 개수} = N 이 되는지를 확인하면 된다.
    • 우선 모든 x≤n 에 대해서, x의 배수의 개수를 세어둔다. O(nlogn)이 걸린다
    • 그러면 {x의 배수의 개수} + {y의 배수의 개수} - {lcm(x,y)의 배수의 개수}를 계산하는 것은 lcm을 구하는 O(logn)에 바운드 된다. 모든 (x,y) 에 대해서 처리하면 총 O(n^2logn)이 걸린다. 대충 구현했을때는 3660ms 정도에 돌아갔다.
• 정해로 추정되는 방법은 O(logn)이다.
  • 중복된 원소들을 제거하고 난 다음에, 가장 큰 원소를 a1, 두번째로 큰 원소를 a2라고 하면, S'= {a1} 또는 S'={a2} 일 때에 값이 최대가 된다는 것을 관찰을 통해서 알아내는 것이 중요하다.
    • x>y 일때, gcd(x, y) ≤ min(y, x-y) 이고, 그러므로 gcd(x, y) ≤ x/2 라는 것을 생각하면 된다.
    • S' ={a1} 이면, x=a1, y=gcd(a2,a3,…) 이다. x+y > a1 이다
    • S' ={a2} 이면, x=a2, y=gcd(a1,a3,…) 이다. x+y > a2 이다
    • S' = {a1, a2} 이면, x≤a1-a2, y<a2 이므로 x+y < a1 이고, S' ={a1} 일때보다 무조건 작다.
    • S' = {a1, ai, …} 이고 S/S' = {a2, aj,…} 이면, x≤a1/2, y≤a2/2 이므로 x+y ≤ a1/2 + a2/2 < a1 이므로, S' ={a1} 일때보다 무조건 작다
  • 결국, a1과 a2를 찾은 뒤에, gcd(a2,a3,…) 과 gcd(a1,a3,…)을 계산해보기만 하면 된다. 시간복잡도는 O(nlogn)으로 충분하다. 실제로는 272ms 정도에 돌아갔다

"""Solution code for "BOJ 33837. gcd와 set".

- Problem link: https://www.acmicpc.net/problem/33837
- Solution link: http://www.teferi.net/ps/problems/boj/33837

Tags: [math]
"""

import math


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    a_set = set(A)
    if len(a_set) == 1:
        print(A[0] if N == 1 else A[0] * 2)
        return

    answer = 0
    for i in range(1, max(A) + 1):
        val = i + math.gcd(*(a_i for a_i in a_set if a_i % i != 0))
        answer = max(val, answer)

    print(answer)


if __name__ == '__main__':
    main()

"""Solution code for "BOJ 33837. gcd와 set".

- Problem link: https://www.acmicpc.net/problem/33837
- Solution link: http://www.teferi.net/ps/problems/boj/33837

Tags: [math]
"""

import math
import itertools


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    size = max(A) + 1
    elem_counter = [0] * size
    for a_i in A:
        elem_counter[a_i] += 1

    if elem_counter[A[0]] == N:
        print(A[0] if N == 1 else A[0] * 2)
        return

    factor_count = [0] * size
    for i in range(1, size):
        factor_count[i] = sum(elem_counter[i:size:i])

    answer = 0
    for i, j in itertools.combinations(range(1, size), 2):
        count = factor_count[i] + factor_count[j]
        if (lcm := math.lcm(i, j)) < size:
            count -= factor_count[lcm]
        if count == N:
            answer = max(answer, i + j)

    print(answer)


if __name__ == '__main__':
    main()

"""Solution code for "BOJ 33837. gcd와 set".

- Problem link: https://www.acmicpc.net/problem/33837
- Solution link: http://www.teferi.net/ps/problems/boj/33837

Tags: [math]
"""

import math


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    a_set = set(A)
    if len(a_set) == 1:
        print(A[0] if N == 1 else A[0] * 2)
        return

    max_elem = max(a_set)
    a_set.discard(max_elem)
    sec_max_elem = max(a_set)
    a_set.discard(sec_max_elem)

    g = math.gcd(*a_set)
    s1 = max_elem + math.gcd(sec_max_elem, g)
    s2 = sec_max_elem + math.gcd(max_elem, g)

    print(max(s1, s2))


if __name__ == '__main__':
    main()