[백준/Python]9613_GCD 합

문제

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

9613번: GCD 합

풀이

유클리드 호제법을 이용합니다.

유클리드 호제법은 a, b(a>b) 두 수가 있을 때, a와 b의 최대공약수 G는 b와 a%b의 최대공약수 G'과 같다는 알고리즘입니다.

코드

import sys
from itertools import combinations


def GCD(A: int, B: int) -> int:
    if B == 0:
        return A
    return GCD(B, A % B)


t = int(sys.stdin.readline().rstrip())
for _ in range(t):
    lst = list(map(int, sys.stdin.readline().rstrip().split()))
    n = lst[0]
    numbers = lst[1:]
    if n == 1:
        continue
    candidates = list(combinations(numbers, 2))
    result = 0
    for candidate in candidates:
        a, b = candidate
        if b > a:
            a, b = b, a
        temp = GCD(a, b)
        result += temp
    print(result)